[PATCH] Really __nocast-annotate kmalloc_node()
[linux-2.6.git] / include / asm-mips / bitops.h
1 /*
2  * This file is subject to the terms and conditions of the GNU General Public
3  * License.  See the file "COPYING" in the main directory of this archive
4  * for more details.
5  *
6  * Copyright (c) 1994 - 1997, 1999, 2000  Ralf Baechle (ralf@gnu.org)
7  * Copyright (c) 1999, 2000  Silicon Graphics, Inc.
8  */
9 #ifndef _ASM_BITOPS_H
10 #define _ASM_BITOPS_H
11
12 #include <linux/config.h>
13 #include <linux/compiler.h>
14 #include <linux/types.h>
15 #include <asm/byteorder.h>              /* sigh ... */
16 #include <asm/cpu-features.h>
17
18 #if (_MIPS_SZLONG == 32)
19 #define SZLONG_LOG 5
20 #define SZLONG_MASK 31UL
21 #define __LL    "ll     "
22 #define __SC    "sc     "
23 #define cpu_to_lelongp(x) cpu_to_le32p((__u32 *) (x)) 
24 #elif (_MIPS_SZLONG == 64)
25 #define SZLONG_LOG 6
26 #define SZLONG_MASK 63UL
27 #define __LL    "lld    "
28 #define __SC    "scd    "
29 #define cpu_to_lelongp(x) cpu_to_le64p((__u64 *) (x)) 
30 #endif
31
32 #ifdef __KERNEL__
33
34 #include <asm/interrupt.h>
35 #include <asm/sgidefs.h>
36 #include <asm/war.h>
37
38 /*
39  * clear_bit() doesn't provide any barrier for the compiler.
40  */
41 #define smp_mb__before_clear_bit()      smp_mb()
42 #define smp_mb__after_clear_bit()       smp_mb()
43
44 /*
45  * Only disable interrupt for kernel mode stuff to keep usermode stuff
46  * that dares to use kernel include files alive.
47  */
48
49 #define __bi_flags                      unsigned long flags
50 #define __bi_local_irq_save(x)          local_irq_save(x)
51 #define __bi_local_irq_restore(x)       local_irq_restore(x)
52 #else
53 #define __bi_flags
54 #define __bi_local_irq_save(x)
55 #define __bi_local_irq_restore(x)
56 #endif /* __KERNEL__ */
57
58 /*
59  * set_bit - Atomically set a bit in memory
60  * @nr: the bit to set
61  * @addr: the address to start counting from
62  *
63  * This function is atomic and may not be reordered.  See __set_bit()
64  * if you do not require the atomic guarantees.
65  * Note that @nr may be almost arbitrarily large; this function is not
66  * restricted to acting on a single-word quantity.
67  */
68 static inline void set_bit(unsigned long nr, volatile unsigned long *addr)
69 {
70         unsigned long *m = ((unsigned long *) addr) + (nr >> SZLONG_LOG);
71         unsigned long temp;
72
73         if (cpu_has_llsc && R10000_LLSC_WAR) {
74                 __asm__ __volatile__(
75                 "1:     " __LL "%0, %1                  # set_bit       \n"
76                 "       or      %0, %2                                  \n"
77                 "       "__SC   "%0, %1                                 \n"
78                 "       beqzl   %0, 1b                                  \n"
79                 : "=&r" (temp), "=m" (*m)
80                 : "ir" (1UL << (nr & SZLONG_MASK)), "m" (*m));
81         } else if (cpu_has_llsc) {
82                 __asm__ __volatile__(
83                 "1:     " __LL "%0, %1                  # set_bit       \n"
84                 "       or      %0, %2                                  \n"
85                 "       "__SC   "%0, %1                                 \n"
86                 "       beqz    %0, 1b                                  \n"
87                 : "=&r" (temp), "=m" (*m)
88                 : "ir" (1UL << (nr & SZLONG_MASK)), "m" (*m));
89         } else {
90                 volatile unsigned long *a = addr;
91                 unsigned long mask;
92                 __bi_flags;
93
94                 a += nr >> SZLONG_LOG;
95                 mask = 1UL << (nr & SZLONG_MASK);
96                 __bi_local_irq_save(flags);
97                 *a |= mask;
98                 __bi_local_irq_restore(flags);
99         }
100 }
101
102 /*
103  * __set_bit - Set a bit in memory
104  * @nr: the bit to set
105  * @addr: the address to start counting from
106  *
107  * Unlike set_bit(), this function is non-atomic and may be reordered.
108  * If it's called on the same region of memory simultaneously, the effect
109  * may be that only one operation succeeds.
110  */
111 static inline void __set_bit(unsigned long nr, volatile unsigned long * addr)
112 {
113         unsigned long * m = ((unsigned long *) addr) + (nr >> SZLONG_LOG);
114
115         *m |= 1UL << (nr & SZLONG_MASK);
116 }
117
118 /*
119  * clear_bit - Clears a bit in memory
120  * @nr: Bit to clear
121  * @addr: Address to start counting from
122  *
123  * clear_bit() is atomic and may not be reordered.  However, it does
124  * not contain a memory barrier, so if it is used for locking purposes,
125  * you should call smp_mb__before_clear_bit() and/or smp_mb__after_clear_bit()
126  * in order to ensure changes are visible on other processors.
127  */
128 static inline void clear_bit(unsigned long nr, volatile unsigned long *addr)
129 {
130         unsigned long *m = ((unsigned long *) addr) + (nr >> SZLONG_LOG);
131         unsigned long temp;
132
133         if (cpu_has_llsc && R10000_LLSC_WAR) {
134                 __asm__ __volatile__(
135                 "1:     " __LL "%0, %1                  # clear_bit     \n"
136                 "       and     %0, %2                                  \n"
137                 "       " __SC "%0, %1                                  \n"
138                 "       beqzl   %0, 1b                                  \n"
139                 : "=&r" (temp), "=m" (*m)
140                 : "ir" (~(1UL << (nr & SZLONG_MASK))), "m" (*m));
141         } else if (cpu_has_llsc) {
142                 __asm__ __volatile__(
143                 "1:     " __LL "%0, %1                  # clear_bit     \n"
144                 "       and     %0, %2                                  \n"
145                 "       " __SC "%0, %1                                  \n"
146                 "       beqz    %0, 1b                                  \n"
147                 : "=&r" (temp), "=m" (*m)
148                 : "ir" (~(1UL << (nr & SZLONG_MASK))), "m" (*m));
149         } else {
150                 volatile unsigned long *a = addr;
151                 unsigned long mask;
152                 __bi_flags;
153
154                 a += nr >> SZLONG_LOG;
155                 mask = 1UL << (nr & SZLONG_MASK);
156                 __bi_local_irq_save(flags);
157                 *a &= ~mask;
158                 __bi_local_irq_restore(flags);
159         }
160 }
161
162 /*
163  * __clear_bit - Clears a bit in memory
164  * @nr: Bit to clear
165  * @addr: Address to start counting from
166  *
167  * Unlike clear_bit(), this function is non-atomic and may be reordered.
168  * If it's called on the same region of memory simultaneously, the effect
169  * may be that only one operation succeeds.
170  */
171 static inline void __clear_bit(unsigned long nr, volatile unsigned long * addr)
172 {
173         unsigned long * m = ((unsigned long *) addr) + (nr >> SZLONG_LOG);
174
175         *m &= ~(1UL << (nr & SZLONG_MASK));
176 }
177
178 /*
179  * change_bit - Toggle a bit in memory
180  * @nr: Bit to change
181  * @addr: Address to start counting from
182  *
183  * change_bit() is atomic and may not be reordered.
184  * Note that @nr may be almost arbitrarily large; this function is not
185  * restricted to acting on a single-word quantity.
186  */
187 static inline void change_bit(unsigned long nr, volatile unsigned long *addr)
188 {
189         if (cpu_has_llsc && R10000_LLSC_WAR) {
190                 unsigned long *m = ((unsigned long *) addr) + (nr >> SZLONG_LOG);
191                 unsigned long temp;
192
193                 __asm__ __volatile__(
194                 "1:     " __LL "%0, %1          # change_bit    \n"
195                 "       xor     %0, %2                          \n"
196                 "       "__SC   "%0, %1                         \n"
197                 "       beqzl   %0, 1b                          \n"
198                 : "=&r" (temp), "=m" (*m)
199                 : "ir" (1UL << (nr & SZLONG_MASK)), "m" (*m));
200         } else if (cpu_has_llsc) {
201                 unsigned long *m = ((unsigned long *) addr) + (nr >> SZLONG_LOG);
202                 unsigned long temp;
203
204                 __asm__ __volatile__(
205                 "1:     " __LL "%0, %1          # change_bit    \n"
206                 "       xor     %0, %2                          \n"
207                 "       "__SC   "%0, %1                         \n"
208                 "       beqz    %0, 1b                          \n"
209                 : "=&r" (temp), "=m" (*m)
210                 : "ir" (1UL << (nr & SZLONG_MASK)), "m" (*m));
211         } else {
212                 volatile unsigned long *a = addr;
213                 unsigned long mask;
214                 __bi_flags;
215
216                 a += nr >> SZLONG_LOG;
217                 mask = 1UL << (nr & SZLONG_MASK);
218                 __bi_local_irq_save(flags);
219                 *a ^= mask;
220                 __bi_local_irq_restore(flags);
221         }
222 }
223
224 /*
225  * __change_bit - Toggle a bit in memory
226  * @nr: the bit to change
227  * @addr: the address to start counting from
228  *
229  * Unlike change_bit(), this function is non-atomic and may be reordered.
230  * If it's called on the same region of memory simultaneously, the effect
231  * may be that only one operation succeeds.
232  */
233 static inline void __change_bit(unsigned long nr, volatile unsigned long * addr)
234 {
235         unsigned long * m = ((unsigned long *) addr) + (nr >> SZLONG_LOG);
236
237         *m ^= 1UL << (nr & SZLONG_MASK);
238 }
239
240 /*
241  * test_and_set_bit - Set a bit and return its old value
242  * @nr: Bit to set
243  * @addr: Address to count from
244  *
245  * This operation is atomic and cannot be reordered.
246  * It also implies a memory barrier.
247  */
248 static inline int test_and_set_bit(unsigned long nr,
249         volatile unsigned long *addr)
250 {
251         if (cpu_has_llsc && R10000_LLSC_WAR) {
252                 unsigned long *m = ((unsigned long *) addr) + (nr >> SZLONG_LOG);
253                 unsigned long temp, res;
254
255                 __asm__ __volatile__(
256                 "1:     " __LL "%0, %1          # test_and_set_bit      \n"
257                 "       or      %2, %0, %3                              \n"
258                 "       " __SC  "%2, %1                                 \n"
259                 "       beqzl   %2, 1b                                  \n"
260                 "       and     %2, %0, %3                              \n"
261 #ifdef CONFIG_SMP
262                 "sync                                                   \n"
263 #endif
264                 : "=&r" (temp), "=m" (*m), "=&r" (res)
265                 : "r" (1UL << (nr & SZLONG_MASK)), "m" (*m)
266                 : "memory");
267
268                 return res != 0;
269         } else if (cpu_has_llsc) {
270                 unsigned long *m = ((unsigned long *) addr) + (nr >> SZLONG_LOG);
271                 unsigned long temp, res;
272
273                 __asm__ __volatile__(
274                 "       .set    noreorder       # test_and_set_bit      \n"
275                 "1:     " __LL "%0, %1                                  \n"
276                 "       or      %2, %0, %3                              \n"
277                 "       " __SC  "%2, %1                                 \n"
278                 "       beqz    %2, 1b                                  \n"
279                 "        and    %2, %0, %3                              \n"
280 #ifdef CONFIG_SMP
281                 "sync                                                   \n"
282 #endif
283                 ".set\treorder"
284                 : "=&r" (temp), "=m" (*m), "=&r" (res)
285                 : "r" (1UL << (nr & SZLONG_MASK)), "m" (*m)
286                 : "memory");
287
288                 return res != 0;
289         } else {
290                 volatile unsigned long *a = addr;
291                 unsigned long mask;
292                 int retval;
293                 __bi_flags;
294
295                 a += nr >> SZLONG_LOG;
296                 mask = 1UL << (nr & SZLONG_MASK);
297                 __bi_local_irq_save(flags);
298                 retval = (mask & *a) != 0;
299                 *a |= mask;
300                 __bi_local_irq_restore(flags);
301
302                 return retval;
303         }
304 }
305
306 /*
307  * __test_and_set_bit - Set a bit and return its old value
308  * @nr: Bit to set
309  * @addr: Address to count from
310  *
311  * This operation is non-atomic and can be reordered.
312  * If two examples of this operation race, one can appear to succeed
313  * but actually fail.  You must protect multiple accesses with a lock.
314  */
315 static inline int __test_and_set_bit(unsigned long nr,
316         volatile unsigned long *addr)
317 {
318         volatile unsigned long *a = addr;
319         unsigned long mask;
320         int retval;
321
322         a += nr >> SZLONG_LOG;
323         mask = 1UL << (nr & SZLONG_MASK);
324         retval = (mask & *a) != 0;
325         *a |= mask;
326
327         return retval;
328 }
329
330 /*
331  * test_and_clear_bit - Clear a bit and return its old value
332  * @nr: Bit to clear
333  * @addr: Address to count from
334  *
335  * This operation is atomic and cannot be reordered.
336  * It also implies a memory barrier.
337  */
338 static inline int test_and_clear_bit(unsigned long nr,
339         volatile unsigned long *addr)
340 {
341         if (cpu_has_llsc && R10000_LLSC_WAR) {
342                 unsigned long *m = ((unsigned long *) addr) + (nr >> SZLONG_LOG);
343                 unsigned long temp, res;
344
345                 __asm__ __volatile__(
346                 "1:     " __LL  "%0, %1         # test_and_clear_bit    \n"
347                 "       or      %2, %0, %3                              \n"
348                 "       xor     %2, %3                                  \n"
349                         __SC    "%2, %1                                 \n"
350                 "       beqzl   %2, 1b                                  \n"
351                 "       and     %2, %0, %3                              \n"
352 #ifdef CONFIG_SMP
353                 "       sync                                            \n"
354 #endif
355                 : "=&r" (temp), "=m" (*m), "=&r" (res)
356                 : "r" (1UL << (nr & SZLONG_MASK)), "m" (*m)
357                 : "memory");
358
359                 return res != 0;
360         } else if (cpu_has_llsc) {
361                 unsigned long *m = ((unsigned long *) addr) + (nr >> SZLONG_LOG);
362                 unsigned long temp, res;
363
364                 __asm__ __volatile__(
365                 "       .set    noreorder       # test_and_clear_bit    \n"
366                 "1:     " __LL  "%0, %1                                 \n"
367                 "       or      %2, %0, %3                              \n"
368                 "       xor     %2, %3                                  \n"
369                         __SC    "%2, %1                                 \n"
370                 "       beqz    %2, 1b                                  \n"
371                 "        and    %2, %0, %3                              \n"
372 #ifdef CONFIG_SMP
373                 "       sync                                            \n"
374 #endif
375                 "       .set    reorder                                 \n"
376                 : "=&r" (temp), "=m" (*m), "=&r" (res)
377                 : "r" (1UL << (nr & SZLONG_MASK)), "m" (*m)
378                 : "memory");
379
380                 return res != 0;
381         } else {
382                 volatile unsigned long *a = addr;
383                 unsigned long mask;
384                 int retval;
385                 __bi_flags;
386
387                 a += nr >> SZLONG_LOG;
388                 mask = 1UL << (nr & SZLONG_MASK);
389                 __bi_local_irq_save(flags);
390                 retval = (mask & *a) != 0;
391                 *a &= ~mask;
392                 __bi_local_irq_restore(flags);
393
394                 return retval;
395         }
396 }
397
398 /*
399  * __test_and_clear_bit - Clear a bit and return its old value
400  * @nr: Bit to clear
401  * @addr: Address to count from
402  *
403  * This operation is non-atomic and can be reordered.
404  * If two examples of this operation race, one can appear to succeed
405  * but actually fail.  You must protect multiple accesses with a lock.
406  */
407 static inline int __test_and_clear_bit(unsigned long nr,
408         volatile unsigned long * addr)
409 {
410         volatile unsigned long *a = addr;
411         unsigned long mask;
412         int retval;
413
414         a += (nr >> SZLONG_LOG);
415         mask = 1UL << (nr & SZLONG_MASK);
416         retval = ((mask & *a) != 0);
417         *a &= ~mask;
418
419         return retval;
420 }
421
422 /*
423  * test_and_change_bit - Change a bit and return its old value
424  * @nr: Bit to change
425  * @addr: Address to count from
426  *
427  * This operation is atomic and cannot be reordered.
428  * It also implies a memory barrier.
429  */
430 static inline int test_and_change_bit(unsigned long nr,
431         volatile unsigned long *addr)
432 {
433         if (cpu_has_llsc && R10000_LLSC_WAR) {
434                 unsigned long *m = ((unsigned long *) addr) + (nr >> SZLONG_LOG);
435                 unsigned long temp, res;
436
437                 __asm__ __volatile__(
438                 "1:     " __LL  " %0, %1        # test_and_change_bit   \n"
439                 "       xor     %2, %0, %3                              \n"
440                 "       "__SC   "%2, %1                                 \n"
441                 "       beqzl   %2, 1b                                  \n"
442                 "       and     %2, %0, %3                              \n"
443 #ifdef CONFIG_SMP
444                 "       sync                                            \n"
445 #endif
446                 : "=&r" (temp), "=m" (*m), "=&r" (res)
447                 : "r" (1UL << (nr & SZLONG_MASK)), "m" (*m)
448                 : "memory");
449
450                 return res != 0;
451         } else if (cpu_has_llsc) {
452                 unsigned long *m = ((unsigned long *) addr) + (nr >> SZLONG_LOG);
453                 unsigned long temp, res;
454
455                 __asm__ __volatile__(
456                 "       .set    noreorder       # test_and_change_bit   \n"
457                 "1:     " __LL  " %0, %1                                \n"
458                 "       xor     %2, %0, %3                              \n"
459                 "       "__SC   "\t%2, %1                               \n"
460                 "       beqz    %2, 1b                                  \n"
461                 "        and    %2, %0, %3                              \n"
462 #ifdef CONFIG_SMP
463                 "       sync                                            \n"
464 #endif
465                 "       .set    reorder                                 \n"
466                 : "=&r" (temp), "=m" (*m), "=&r" (res)
467                 : "r" (1UL << (nr & SZLONG_MASK)), "m" (*m)
468                 : "memory");
469
470                 return res != 0;
471         } else {
472                 volatile unsigned long *a = addr;
473                 unsigned long mask, retval;
474                 __bi_flags;
475
476                 a += nr >> SZLONG_LOG;
477                 mask = 1UL << (nr & SZLONG_MASK);
478                 __bi_local_irq_save(flags);
479                 retval = (mask & *a) != 0;
480                 *a ^= mask;
481                 __bi_local_irq_restore(flags);
482
483                 return retval;
484         }
485 }
486
487 /*
488  * __test_and_change_bit - Change a bit and return its old value
489  * @nr: Bit to change
490  * @addr: Address to count from
491  *
492  * This operation is non-atomic and can be reordered.
493  * If two examples of this operation race, one can appear to succeed
494  * but actually fail.  You must protect multiple accesses with a lock.
495  */
496 static inline int __test_and_change_bit(unsigned long nr,
497         volatile unsigned long *addr)
498 {
499         volatile unsigned long *a = addr;
500         unsigned long mask;
501         int retval;
502
503         a += (nr >> SZLONG_LOG);
504         mask = 1UL << (nr & SZLONG_MASK);
505         retval = ((mask & *a) != 0);
506         *a ^= mask;
507
508         return retval;
509 }
510
511 #undef __bi_flags
512 #undef __bi_local_irq_save
513 #undef __bi_local_irq_restore
514
515 /*
516  * test_bit - Determine whether a bit is set
517  * @nr: bit number to test
518  * @addr: Address to start counting from
519  */
520 static inline int test_bit(unsigned long nr, const volatile unsigned long *addr)
521 {
522         return 1UL & (addr[nr >> SZLONG_LOG] >> (nr & SZLONG_MASK));
523 }
524
525 /*
526  * ffz - find first zero in word.
527  * @word: The word to search
528  *
529  * Undefined if no zero exists, so code should check against ~0UL first.
530  */
531 static inline unsigned long ffz(unsigned long word)
532 {
533         int b = 0, s;
534
535         word = ~word;
536 #ifdef CONFIG_MIPS32
537         s = 16; if (word << 16 != 0) s = 0; b += s; word >>= s;
538         s =  8; if (word << 24 != 0) s = 0; b += s; word >>= s;
539         s =  4; if (word << 28 != 0) s = 0; b += s; word >>= s;
540         s =  2; if (word << 30 != 0) s = 0; b += s; word >>= s;
541         s =  1; if (word << 31 != 0) s = 0; b += s;
542 #endif
543 #ifdef CONFIG_MIPS64
544         s = 32; if (word << 32 != 0) s = 0; b += s; word >>= s;
545         s = 16; if (word << 48 != 0) s = 0; b += s; word >>= s;
546         s =  8; if (word << 56 != 0) s = 0; b += s; word >>= s;
547         s =  4; if (word << 60 != 0) s = 0; b += s; word >>= s;
548         s =  2; if (word << 62 != 0) s = 0; b += s; word >>= s;
549         s =  1; if (word << 63 != 0) s = 0; b += s;
550 #endif
551
552         return b;
553 }
554
555 /*
556  * __ffs - find first bit in word.
557  * @word: The word to search
558  *
559  * Undefined if no bit exists, so code should check against 0 first.
560  */
561 static inline unsigned long __ffs(unsigned long word)
562 {
563         return ffz(~word);
564 }
565
566 /*
567  * fls: find last bit set.
568  */
569
570 #define fls(x) generic_fls(x)
571
572 /*
573  * find_next_zero_bit - find the first zero bit in a memory region
574  * @addr: The address to base the search on
575  * @offset: The bitnumber to start searching at
576  * @size: The maximum size to search
577  */
578 static inline unsigned long find_next_zero_bit(const unsigned long *addr,
579         unsigned long size, unsigned long offset)
580 {
581         const unsigned long *p = addr + (offset >> SZLONG_LOG);
582         unsigned long result = offset & ~SZLONG_MASK;
583         unsigned long tmp;
584
585         if (offset >= size)
586                 return size;
587         size -= result;
588         offset &= SZLONG_MASK;
589         if (offset) {
590                 tmp = *(p++);
591                 tmp |= ~0UL >> (_MIPS_SZLONG-offset);
592                 if (size < _MIPS_SZLONG)
593                         goto found_first;
594                 if (~tmp)
595                         goto found_middle;
596                 size -= _MIPS_SZLONG;
597                 result += _MIPS_SZLONG;
598         }
599         while (size & ~SZLONG_MASK) {
600                 if (~(tmp = *(p++)))
601                         goto found_middle;
602                 result += _MIPS_SZLONG;
603                 size -= _MIPS_SZLONG;
604         }
605         if (!size)
606                 return result;
607         tmp = *p;
608
609 found_first:
610         tmp |= ~0UL << size;
611         if (tmp == ~0UL)                /* Are any bits zero? */
612                 return result + size;   /* Nope. */
613 found_middle:
614         return result + ffz(tmp);
615 }
616
617 #define find_first_zero_bit(addr, size) \
618         find_next_zero_bit((addr), (size), 0)
619
620 /*
621  * find_next_bit - find the next set bit in a memory region
622  * @addr: The address to base the search on
623  * @offset: The bitnumber to start searching at
624  * @size: The maximum size to search
625  */
626 static inline unsigned long find_next_bit(const unsigned long *addr,
627         unsigned long size, unsigned long offset)
628 {
629         const unsigned long *p = addr + (offset >> SZLONG_LOG);
630         unsigned long result = offset & ~SZLONG_MASK;
631         unsigned long tmp;
632
633         if (offset >= size)
634                 return size;
635         size -= result;
636         offset &= SZLONG_MASK;
637         if (offset) {
638                 tmp = *(p++);
639                 tmp &= ~0UL << offset;
640                 if (size < _MIPS_SZLONG)
641                         goto found_first;
642                 if (tmp)
643                         goto found_middle;
644                 size -= _MIPS_SZLONG;
645                 result += _MIPS_SZLONG;
646         }
647         while (size & ~SZLONG_MASK) {
648                 if ((tmp = *(p++)))
649                         goto found_middle;
650                 result += _MIPS_SZLONG;
651                 size -= _MIPS_SZLONG;
652         }
653         if (!size)
654                 return result;
655         tmp = *p;
656
657 found_first:
658         tmp &= ~0UL >> (_MIPS_SZLONG - size);
659         if (tmp == 0UL)                 /* Are any bits set? */
660                 return result + size;   /* Nope. */
661 found_middle:
662         return result + __ffs(tmp);
663 }
664
665 /*
666  * find_first_bit - find the first set bit in a memory region
667  * @addr: The address to start the search at
668  * @size: The maximum size to search
669  *
670  * Returns the bit-number of the first set bit, not the number of the byte
671  * containing a bit.
672  */
673 #define find_first_bit(addr, size) \
674         find_next_bit((addr), (size), 0)
675
676 #ifdef __KERNEL__
677
678 /*
679  * Every architecture must define this function. It's the fastest
680  * way of searching a 140-bit bitmap where the first 100 bits are
681  * unlikely to be set. It's guaranteed that at least one of the 140
682  * bits is cleared.
683  */
684 static inline int sched_find_first_bit(const unsigned long *b)
685 {
686 #ifdef CONFIG_MIPS32
687         if (unlikely(b[0]))
688                 return __ffs(b[0]);
689         if (unlikely(b[1]))
690                 return __ffs(b[1]) + 32;
691         if (unlikely(b[2]))
692                 return __ffs(b[2]) + 64;
693         if (b[3])
694                 return __ffs(b[3]) + 96;
695         return __ffs(b[4]) + 128;
696 #endif
697 #ifdef CONFIG_MIPS64
698         if (unlikely(b[0]))
699                 return __ffs(b[0]);
700         if (unlikely(b[1]))
701                 return __ffs(b[1]) + 64;
702         return __ffs(b[2]) + 128;
703 #endif
704 }
705
706 /*
707  * ffs - find first bit set
708  * @x: the word to search
709  *
710  * This is defined the same way as
711  * the libc and compiler builtin ffs routines, therefore
712  * differs in spirit from the above ffz (man ffs).
713  */
714
715 #define ffs(x) generic_ffs(x)
716
717 /*
718  * hweightN - returns the hamming weight of a N-bit word
719  * @x: the word to weigh
720  *
721  * The Hamming Weight of a number is the total number of bits set in it.
722  */
723
724 #define hweight64(x)    generic_hweight64(x)
725 #define hweight32(x)    generic_hweight32(x)
726 #define hweight16(x)    generic_hweight16(x)
727 #define hweight8(x)     generic_hweight8(x)
728
729 static inline int __test_and_set_le_bit(unsigned long nr, unsigned long *addr)
730 {
731         unsigned char   *ADDR = (unsigned char *) addr;
732         int             mask, retval;
733
734         ADDR += nr >> 3;
735         mask = 1 << (nr & 0x07);
736         retval = (mask & *ADDR) != 0;
737         *ADDR |= mask;
738
739         return retval;
740 }
741
742 static inline int __test_and_clear_le_bit(unsigned long nr, unsigned long *addr)
743 {
744         unsigned char   *ADDR = (unsigned char *) addr;
745         int             mask, retval;
746
747         ADDR += nr >> 3;
748         mask = 1 << (nr & 0x07);
749         retval = (mask & *ADDR) != 0;
750         *ADDR &= ~mask;
751
752         return retval;
753 }
754
755 static inline int test_le_bit(unsigned long nr, const unsigned long * addr)
756 {
757         const unsigned char     *ADDR = (const unsigned char *) addr;
758         int                     mask;
759
760         ADDR += nr >> 3;
761         mask = 1 << (nr & 0x07);
762
763         return ((mask & *ADDR) != 0);
764 }
765
766 static inline unsigned long find_next_zero_le_bit(unsigned long *addr,
767         unsigned long size, unsigned long offset)
768 {
769         unsigned long *p = ((unsigned long *) addr) + (offset >> SZLONG_LOG);
770         unsigned long result = offset & ~SZLONG_MASK;
771         unsigned long tmp;
772
773         if (offset >= size)
774                 return size;
775         size -= result;
776         offset &= SZLONG_MASK;
777         if (offset) {
778                 tmp = cpu_to_lelongp(p++);
779                 tmp |= ~0UL >> (_MIPS_SZLONG-offset); /* bug or feature ? */
780                 if (size < _MIPS_SZLONG)
781                         goto found_first;
782                 if (~tmp)
783                         goto found_middle;
784                 size -= _MIPS_SZLONG;
785                 result += _MIPS_SZLONG;
786         }
787         while (size & ~SZLONG_MASK) {
788                 if (~(tmp = cpu_to_lelongp(p++)))
789                         goto found_middle;
790                 result += _MIPS_SZLONG;
791                 size -= _MIPS_SZLONG;
792         }
793         if (!size)
794                 return result;
795         tmp = cpu_to_lelongp(p);
796
797 found_first:
798         tmp |= ~0UL << size;
799         if (tmp == ~0UL)                /* Are any bits zero? */
800                 return result + size;   /* Nope. */
801
802 found_middle:
803         return result + ffz(tmp);
804 }
805
806 #define find_first_zero_le_bit(addr, size) \
807         find_next_zero_le_bit((addr), (size), 0)
808
809 #define ext2_set_bit(nr,addr) \
810         __test_and_set_le_bit((nr),(unsigned long*)addr)
811 #define ext2_clear_bit(nr, addr) \
812         __test_and_clear_le_bit((nr),(unsigned long*)addr)
813  #define ext2_set_bit_atomic(lock, nr, addr)            \
814 ({                                                      \
815         int ret;                                        \
816         spin_lock(lock);                                \
817         ret = ext2_set_bit((nr), (addr));               \
818         spin_unlock(lock);                              \
819         ret;                                            \
820 })
821
822 #define ext2_clear_bit_atomic(lock, nr, addr)           \
823 ({                                                      \
824         int ret;                                        \
825         spin_lock(lock);                                \
826         ret = ext2_clear_bit((nr), (addr));             \
827         spin_unlock(lock);                              \
828         ret;                                            \
829 })
830 #define ext2_test_bit(nr, addr) test_le_bit((nr),(unsigned long*)addr)
831 #define ext2_find_first_zero_bit(addr, size) \
832         find_first_zero_le_bit((unsigned long*)addr, size)
833 #define ext2_find_next_zero_bit(addr, size, off) \
834         find_next_zero_le_bit((unsigned long*)addr, size, off)
835
836 /*
837  * Bitmap functions for the minix filesystem.
838  *
839  * FIXME: These assume that Minix uses the native byte/bitorder.
840  * This limits the Minix filesystem's value for data exchange very much.
841  */
842 #define minix_test_and_set_bit(nr,addr) test_and_set_bit(nr,addr)
843 #define minix_set_bit(nr,addr) set_bit(nr,addr)
844 #define minix_test_and_clear_bit(nr,addr) test_and_clear_bit(nr,addr)
845 #define minix_test_bit(nr,addr) test_bit(nr,addr)
846 #define minix_find_first_zero_bit(addr,size) find_first_zero_bit(addr,size)
847
848 #endif /* __KERNEL__ */
849
850 #endif /* _ASM_BITOPS_H */