blob: 7d20b95edb3bcc1942d0e4fb0237a6534af3b227 [file] [log] [blame]
Linus Torvalds1da177e2005-04-16 15:20:36 -07001#ifndef _I386_BITOPS_H
2#define _I386_BITOPS_H
3
4/*
5 * Copyright 1992, Linus Torvalds.
6 */
7
8#include <linux/config.h>
9#include <linux/compiler.h>
Gerd Hoffmann9a0b5812006-03-23 02:59:32 -080010#include <asm/alternative.h>
Linus Torvalds1da177e2005-04-16 15:20:36 -070011
12/*
13 * These have to be done with inline assembly: that way the bit-setting
14 * is guaranteed to be atomic. All bit operations return 0 if the bit
15 * was cleared before the operation and != 0 if it was not.
16 *
17 * bit 0 is the LSB of addr; bit 32 is the LSB of (addr+1).
18 */
19
Linus Torvalds1da177e2005-04-16 15:20:36 -070020#define ADDR (*(volatile long *) addr)
21
22/**
23 * set_bit - Atomically set a bit in memory
24 * @nr: the bit to set
25 * @addr: the address to start counting from
26 *
27 * This function is atomic and may not be reordered. See __set_bit()
28 * if you do not require the atomic guarantees.
29 *
30 * Note: there are no guarantees that this function will not be reordered
31 * on non x86 architectures, so if you are writting portable code,
32 * make sure not to rely on its reordering guarantees.
33 *
34 * Note that @nr may be almost arbitrarily large; this function is not
35 * restricted to acting on a single-word quantity.
36 */
37static inline void set_bit(int nr, volatile unsigned long * addr)
38{
39 __asm__ __volatile__( LOCK_PREFIX
40 "btsl %1,%0"
Andi Kleen92934bc2006-01-11 22:42:32 +010041 :"+m" (ADDR)
Linus Torvalds1da177e2005-04-16 15:20:36 -070042 :"Ir" (nr));
43}
44
45/**
46 * __set_bit - Set a bit in memory
47 * @nr: the bit to set
48 * @addr: the address to start counting from
49 *
50 * Unlike set_bit(), this function is non-atomic and may be reordered.
51 * If it's called on the same region of memory simultaneously, the effect
52 * may be that only one operation succeeds.
53 */
54static inline void __set_bit(int nr, volatile unsigned long * addr)
55{
56 __asm__(
57 "btsl %1,%0"
Andi Kleen92934bc2006-01-11 22:42:32 +010058 :"+m" (ADDR)
Linus Torvalds1da177e2005-04-16 15:20:36 -070059 :"Ir" (nr));
60}
61
62/**
63 * clear_bit - Clears a bit in memory
64 * @nr: Bit to clear
65 * @addr: Address to start counting from
66 *
67 * clear_bit() is atomic and may not be reordered. However, it does
68 * not contain a memory barrier, so if it is used for locking purposes,
69 * you should call smp_mb__before_clear_bit() and/or smp_mb__after_clear_bit()
70 * in order to ensure changes are visible on other processors.
71 */
72static inline void clear_bit(int nr, volatile unsigned long * addr)
73{
74 __asm__ __volatile__( LOCK_PREFIX
75 "btrl %1,%0"
Andi Kleen92934bc2006-01-11 22:42:32 +010076 :"+m" (ADDR)
Linus Torvalds1da177e2005-04-16 15:20:36 -070077 :"Ir" (nr));
78}
79
80static inline void __clear_bit(int nr, volatile unsigned long * addr)
81{
82 __asm__ __volatile__(
83 "btrl %1,%0"
Andi Kleen92934bc2006-01-11 22:42:32 +010084 :"+m" (ADDR)
Linus Torvalds1da177e2005-04-16 15:20:36 -070085 :"Ir" (nr));
86}
87#define smp_mb__before_clear_bit() barrier()
88#define smp_mb__after_clear_bit() barrier()
89
90/**
91 * __change_bit - Toggle a bit in memory
92 * @nr: the bit to change
93 * @addr: the address to start counting from
94 *
95 * Unlike change_bit(), this function is non-atomic and may be reordered.
96 * If it's called on the same region of memory simultaneously, the effect
97 * may be that only one operation succeeds.
98 */
99static inline void __change_bit(int nr, volatile unsigned long * addr)
100{
101 __asm__ __volatile__(
102 "btcl %1,%0"
Andi Kleen92934bc2006-01-11 22:42:32 +0100103 :"+m" (ADDR)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700104 :"Ir" (nr));
105}
106
107/**
108 * change_bit - Toggle a bit in memory
109 * @nr: Bit to change
110 * @addr: Address to start counting from
111 *
112 * change_bit() is atomic and may not be reordered. It may be
113 * reordered on other architectures than x86.
114 * Note that @nr may be almost arbitrarily large; this function is not
115 * restricted to acting on a single-word quantity.
116 */
117static inline void change_bit(int nr, volatile unsigned long * addr)
118{
119 __asm__ __volatile__( LOCK_PREFIX
120 "btcl %1,%0"
Andi Kleen92934bc2006-01-11 22:42:32 +0100121 :"+m" (ADDR)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700122 :"Ir" (nr));
123}
124
125/**
126 * test_and_set_bit - Set a bit and return its old value
127 * @nr: Bit to set
128 * @addr: Address to count from
129 *
130 * This operation is atomic and cannot be reordered.
131 * It may be reordered on other architectures than x86.
132 * It also implies a memory barrier.
133 */
134static inline int test_and_set_bit(int nr, volatile unsigned long * addr)
135{
136 int oldbit;
137
138 __asm__ __volatile__( LOCK_PREFIX
139 "btsl %2,%1\n\tsbbl %0,%0"
Andi Kleen92934bc2006-01-11 22:42:32 +0100140 :"=r" (oldbit),"+m" (ADDR)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700141 :"Ir" (nr) : "memory");
142 return oldbit;
143}
144
145/**
146 * __test_and_set_bit - Set a bit and return its old value
147 * @nr: Bit to set
148 * @addr: Address to count from
149 *
150 * This operation is non-atomic and can be reordered.
151 * If two examples of this operation race, one can appear to succeed
152 * but actually fail. You must protect multiple accesses with a lock.
153 */
154static inline int __test_and_set_bit(int nr, volatile unsigned long * addr)
155{
156 int oldbit;
157
158 __asm__(
159 "btsl %2,%1\n\tsbbl %0,%0"
Andi Kleen92934bc2006-01-11 22:42:32 +0100160 :"=r" (oldbit),"+m" (ADDR)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700161 :"Ir" (nr));
162 return oldbit;
163}
164
165/**
166 * test_and_clear_bit - Clear a bit and return its old value
167 * @nr: Bit to clear
168 * @addr: Address to count from
169 *
170 * This operation is atomic and cannot be reordered.
171 * It can be reorderdered on other architectures other than x86.
172 * It also implies a memory barrier.
173 */
174static inline int test_and_clear_bit(int nr, volatile unsigned long * addr)
175{
176 int oldbit;
177
178 __asm__ __volatile__( LOCK_PREFIX
179 "btrl %2,%1\n\tsbbl %0,%0"
Andi Kleen92934bc2006-01-11 22:42:32 +0100180 :"=r" (oldbit),"+m" (ADDR)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700181 :"Ir" (nr) : "memory");
182 return oldbit;
183}
184
185/**
186 * __test_and_clear_bit - Clear a bit and return its old value
187 * @nr: Bit to clear
188 * @addr: Address to count from
189 *
190 * This operation is non-atomic and can be reordered.
191 * If two examples of this operation race, one can appear to succeed
192 * but actually fail. You must protect multiple accesses with a lock.
193 */
194static inline int __test_and_clear_bit(int nr, volatile unsigned long *addr)
195{
196 int oldbit;
197
198 __asm__(
199 "btrl %2,%1\n\tsbbl %0,%0"
Andi Kleen92934bc2006-01-11 22:42:32 +0100200 :"=r" (oldbit),"+m" (ADDR)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700201 :"Ir" (nr));
202 return oldbit;
203}
204
205/* WARNING: non atomic and it can be reordered! */
206static inline int __test_and_change_bit(int nr, volatile unsigned long *addr)
207{
208 int oldbit;
209
210 __asm__ __volatile__(
211 "btcl %2,%1\n\tsbbl %0,%0"
Andi Kleen92934bc2006-01-11 22:42:32 +0100212 :"=r" (oldbit),"+m" (ADDR)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700213 :"Ir" (nr) : "memory");
214 return oldbit;
215}
216
217/**
218 * test_and_change_bit - Change a bit and return its old value
219 * @nr: Bit to change
220 * @addr: Address to count from
221 *
222 * This operation is atomic and cannot be reordered.
223 * It also implies a memory barrier.
224 */
225static inline int test_and_change_bit(int nr, volatile unsigned long* addr)
226{
227 int oldbit;
228
229 __asm__ __volatile__( LOCK_PREFIX
230 "btcl %2,%1\n\tsbbl %0,%0"
Andi Kleen92934bc2006-01-11 22:42:32 +0100231 :"=r" (oldbit),"+m" (ADDR)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700232 :"Ir" (nr) : "memory");
233 return oldbit;
234}
235
236#if 0 /* Fool kernel-doc since it doesn't do macros yet */
237/**
238 * test_bit - Determine whether a bit is set
239 * @nr: bit number to test
240 * @addr: Address to start counting from
241 */
242static int test_bit(int nr, const volatile void * addr);
243#endif
244
Ingo Molnar652050a2006-01-14 13:21:30 -0800245static __always_inline int constant_test_bit(int nr, const volatile unsigned long *addr)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700246{
247 return ((1UL << (nr & 31)) & (addr[nr >> 5])) != 0;
248}
249
250static inline int variable_test_bit(int nr, const volatile unsigned long * addr)
251{
252 int oldbit;
253
254 __asm__ __volatile__(
255 "btl %2,%1\n\tsbbl %0,%0"
256 :"=r" (oldbit)
257 :"m" (ADDR),"Ir" (nr));
258 return oldbit;
259}
260
261#define test_bit(nr,addr) \
262(__builtin_constant_p(nr) ? \
263 constant_test_bit((nr),(addr)) : \
264 variable_test_bit((nr),(addr)))
265
266#undef ADDR
267
268/**
269 * find_first_zero_bit - find the first zero bit in a memory region
270 * @addr: The address to start the search at
271 * @size: The maximum size to search
272 *
273 * Returns the bit-number of the first zero bit, not the number of the byte
274 * containing a bit.
275 */
276static inline int find_first_zero_bit(const unsigned long *addr, unsigned size)
277{
278 int d0, d1, d2;
279 int res;
280
281 if (!size)
282 return 0;
283 /* This looks at memory. Mark it volatile to tell gcc not to move it around */
284 __asm__ __volatile__(
285 "movl $-1,%%eax\n\t"
286 "xorl %%edx,%%edx\n\t"
287 "repe; scasl\n\t"
288 "je 1f\n\t"
289 "xorl -4(%%edi),%%eax\n\t"
290 "subl $4,%%edi\n\t"
291 "bsfl %%eax,%%edx\n"
292 "1:\tsubl %%ebx,%%edi\n\t"
293 "shll $3,%%edi\n\t"
294 "addl %%edi,%%edx"
295 :"=d" (res), "=&c" (d0), "=&D" (d1), "=&a" (d2)
296 :"1" ((size + 31) >> 5), "2" (addr), "b" (addr) : "memory");
297 return res;
298}
299
300/**
301 * find_next_zero_bit - find the first zero bit in a memory region
302 * @addr: The address to base the search on
303 * @offset: The bitnumber to start searching at
304 * @size: The maximum size to search
305 */
306int find_next_zero_bit(const unsigned long *addr, int size, int offset);
307
308/**
Steven Rostedtcd85c8b2005-07-28 08:45:06 -0400309 * __ffs - find first bit in word.
310 * @word: The word to search
311 *
312 * Undefined if no bit exists, so code should check against 0 first.
313 */
314static inline unsigned long __ffs(unsigned long word)
315{
316 __asm__("bsfl %1,%0"
317 :"=r" (word)
318 :"rm" (word));
319 return word;
320}
321
322/**
Linus Torvalds1da177e2005-04-16 15:20:36 -0700323 * find_first_bit - find the first set bit in a memory region
324 * @addr: The address to start the search at
325 * @size: The maximum size to search
326 *
327 * Returns the bit-number of the first set bit, not the number of the byte
328 * containing a bit.
329 */
David Howellsd89c1452006-01-06 00:11:59 -0800330static inline unsigned find_first_bit(const unsigned long *addr, unsigned size)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700331{
David Howellsd89c1452006-01-06 00:11:59 -0800332 unsigned x = 0;
Linus Torvaldsd6d2a2a2005-07-29 11:01:22 -0400333
334 while (x < size) {
335 unsigned long val = *addr++;
336 if (val)
337 return __ffs(val) + x;
Steven Rostedtcd85c8b2005-07-28 08:45:06 -0400338 x += (sizeof(*addr)<<3);
Linus Torvaldsd6d2a2a2005-07-29 11:01:22 -0400339 }
Steven Rostedtcd85c8b2005-07-28 08:45:06 -0400340 return x;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700341}
342
343/**
344 * find_next_bit - find the first set bit in a memory region
345 * @addr: The address to base the search on
346 * @offset: The bitnumber to start searching at
347 * @size: The maximum size to search
348 */
349int find_next_bit(const unsigned long *addr, int size, int offset);
350
351/**
352 * ffz - find first zero in word.
353 * @word: The word to search
354 *
355 * Undefined if no zero exists, so code should check against ~0UL first.
356 */
357static inline unsigned long ffz(unsigned long word)
358{
359 __asm__("bsfl %1,%0"
360 :"=r" (word)
361 :"r" (~word));
362 return word;
363}
364
Stephen Hemminger3821af22005-12-21 19:30:53 -0800365#define fls64(x) generic_fls64(x)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700366
367#ifdef __KERNEL__
368
369/*
370 * Every architecture must define this function. It's the fastest
371 * way of searching a 140-bit bitmap where the first 100 bits are
372 * unlikely to be set. It's guaranteed that at least one of the 140
373 * bits is cleared.
374 */
375static inline int sched_find_first_bit(const unsigned long *b)
376{
377 if (unlikely(b[0]))
378 return __ffs(b[0]);
379 if (unlikely(b[1]))
380 return __ffs(b[1]) + 32;
381 if (unlikely(b[2]))
382 return __ffs(b[2]) + 64;
383 if (b[3])
384 return __ffs(b[3]) + 96;
385 return __ffs(b[4]) + 128;
386}
387
388/**
389 * ffs - find first bit set
390 * @x: the word to search
391 *
392 * This is defined the same way as
393 * the libc and compiler builtin ffs routines, therefore
394 * differs in spirit from the above ffz (man ffs).
395 */
396static inline int ffs(int x)
397{
398 int r;
399
400 __asm__("bsfl %1,%0\n\t"
401 "jnz 1f\n\t"
402 "movl $-1,%0\n"
403 "1:" : "=r" (r) : "rm" (x));
404 return r+1;
405}
406
407/**
Stephen Hemmingerd8322452006-01-06 00:12:12 -0800408 * fls - find last bit set
409 * @x: the word to search
410 *
411 * This is defined the same way as ffs.
412 */
413static inline int fls(int x)
414{
415 int r;
416
417 __asm__("bsrl %1,%0\n\t"
418 "jnz 1f\n\t"
419 "movl $-1,%0\n"
420 "1:" : "=r" (r) : "rm" (x));
421 return r+1;
422}
423
424/**
Linus Torvalds1da177e2005-04-16 15:20:36 -0700425 * hweightN - returns the hamming weight of a N-bit word
426 * @x: the word to weigh
427 *
428 * The Hamming Weight of a number is the total number of bits set in it.
429 */
430
431#define hweight32(x) generic_hweight32(x)
432#define hweight16(x) generic_hweight16(x)
433#define hweight8(x) generic_hweight8(x)
434
435#endif /* __KERNEL__ */
436
437#ifdef __KERNEL__
438
439#define ext2_set_bit(nr,addr) \
440 __test_and_set_bit((nr),(unsigned long*)addr)
441#define ext2_set_bit_atomic(lock,nr,addr) \
442 test_and_set_bit((nr),(unsigned long*)addr)
443#define ext2_clear_bit(nr, addr) \
444 __test_and_clear_bit((nr),(unsigned long*)addr)
445#define ext2_clear_bit_atomic(lock,nr, addr) \
446 test_and_clear_bit((nr),(unsigned long*)addr)
447#define ext2_test_bit(nr, addr) test_bit((nr),(unsigned long*)addr)
448#define ext2_find_first_zero_bit(addr, size) \
449 find_first_zero_bit((unsigned long*)addr, size)
450#define ext2_find_next_zero_bit(addr, size, off) \
451 find_next_zero_bit((unsigned long*)addr, size, off)
452
453/* Bitmap functions for the minix filesystem. */
454#define minix_test_and_set_bit(nr,addr) __test_and_set_bit(nr,(void*)addr)
455#define minix_set_bit(nr,addr) __set_bit(nr,(void*)addr)
456#define minix_test_and_clear_bit(nr,addr) __test_and_clear_bit(nr,(void*)addr)
457#define minix_test_bit(nr,addr) test_bit(nr,(void*)addr)
458#define minix_find_first_zero_bit(addr,size) \
459 find_first_zero_bit((void*)addr,size)
460
461#endif /* __KERNEL__ */
462
463#endif /* _I386_BITOPS_H */