BXE: min->MIN, plus an spatch
[akaros.git] / kern / arch / x86 / bitops.h
1 #ifndef _X86_BITOPS_H
2 #define _X86_BITOPS_H
3
4 /*
5  * Copyright 1992, Linus Torvalds.
6  *
7  * Note: inlines with more than a single statement should be marked
8  * __always_inline to avoid problems with older gcc's inlining heuristics.
9  */
10
11 #define BIT_64(n)                       (U64_C(1) << (n))
12 #define DECLARE_BITMAP(name,bits) \
13         unsigned long name[(bits+sizeof(unsigned long)*8 - 1)/(sizeof(unsigned long)*8)/*BITS_TO_LONGS(bits)*/]
14 /*
15  * These have to be done with inline assembly: that way the bit-setting
16  * is guaranteed to be atomic. All bit operations return 0 if the bit
17  * was cleared before the operation and != 0 if it was not.
18  *
19  * bit 0 is the LSB of addr; bit 32 is the LSB of (addr+1).
20  */
21
22 #if __GNUC__ < 4 || (__GNUC__ == 4 && __GNUC_MINOR__ < 1)
23 #error "Get a gcc newer than 4.4.0"
24 #else
25 #define BITOP_ADDR(x) "+m" (*(volatile long *) (x))
26 #endif
27
28 #define ADDR                            BITOP_ADDR(addr)
29
30 #define LOCK_PREFIX "lock "
31 /*
32  * We do the locked ops that don't return the old value as
33  * a mask operation on a byte.
34  */
35 #define IS_IMMEDIATE(nr)                (__builtin_constant_p(nr))
36 #define CONST_MASK_ADDR(nr, addr)       BITOP_ADDR((void *)(addr) + ((nr)>>3))
37 #define CONST_MASK(nr)                  (1 << ((nr) & 7))
38
39 /**
40  * set_bit - Atomically set a bit in memory
41  * @nr: the bit to set
42  * @addr: the address to start counting from
43  *
44  * This function is atomic and may not be reordered.  See __set_bit()
45  * if you do not require the atomic guarantees.
46  *
47  * Note: there are no guarantees that this function will not be reordered
48  * on non x86 architectures, so if you are writing portable code,
49  * make sure not to rely on its reordering guarantees.
50  *
51  * Note that @nr may be almost arbitrarily large; this function is not
52  * restricted to acting on a single-word quantity.
53  */
54 static __always_inline void
55 set_bit(unsigned int nr, volatile unsigned long *addr)
56 {
57         if (IS_IMMEDIATE(nr)) {
58                 asm volatile(LOCK_PREFIX "orb %1,%0"
59                         : CONST_MASK_ADDR(nr, addr)
60                         : "iq" ((uint8_t)CONST_MASK(nr))
61                         : "memory");
62         } else {
63                 asm volatile(LOCK_PREFIX "bts %1,%0"
64                         : BITOP_ADDR(addr) : "Ir" (nr) : "memory");
65         }
66 }
67
68 /**
69  * __set_bit - Set a bit in memory
70  * @nr: the bit to set
71  * @addr: the address to start counting from
72  *
73  * Unlike set_bit(), this function is non-atomic and may be reordered.
74  * If it's called on the same region of memory simultaneously, the effect
75  * may be that only one operation succeeds.
76  */
77 static inline void __set_bit(int nr, volatile unsigned long *addr)
78 {
79         asm volatile("bts %1,%0" : ADDR : "Ir" (nr) : "memory");
80 }
81
82 /**
83  * clear_bit - Clears a bit in memory
84  * @nr: Bit to clear
85  * @addr: Address to start counting from
86  *
87  * clear_bit() is atomic and may not be reordered.  However, it does
88  * not contain a memory barrier, so if it is used for locking purposes,
89  * you should call smp_mb__before_clear_bit() and/or smp_mb__after_clear_bit()
90  * in order to ensure changes are visible on other processors.
91  * 
92  * Note from brho: I think the use of LOCK_PREFIX (assuming it is "lock")
93  * provides a memory barrier against hardware reordering accesses around the
94  * LOCK ("lock" serializes).  This lacks a cmb() (called a barrier() in Linux),
95  * which would prevent the compiler from reordering the instructions.  The
96  * above-mentioned smp_mb__before_clear_bit appears to be this cmb(), so it's
97  * not clear what the usage of "memory barrier" means exactly here and
98  * elsewhere in this file. */
99 static __always_inline void
100 clear_bit(int nr, volatile unsigned long *addr)
101 {
102         if (IS_IMMEDIATE(nr)) {
103                 asm volatile(LOCK_PREFIX "andb %1,%0"
104                         : CONST_MASK_ADDR(nr, addr)
105                         : "iq" ((uint8_t)~CONST_MASK(nr)));
106         } else {
107                 asm volatile(LOCK_PREFIX "btr %1,%0"
108                         : BITOP_ADDR(addr)
109                         : "Ir" (nr));
110         }
111 }
112
113 /*
114  * clear_bit_unlock - Clears a bit in memory
115  * @nr: Bit to clear
116  * @addr: Address to start counting from
117  *
118  * clear_bit() is atomic and implies release semantics before the memory
119  * operation. It can be used for an unlock.
120  */
121 static inline void clear_bit_unlock(unsigned nr, volatile unsigned long *addr)
122 {
123         cmb();
124         clear_bit(nr, addr);
125 }
126
127 static inline void __clear_bit(int nr, volatile unsigned long *addr)
128 {
129         asm volatile("btr %1,%0" : ADDR : "Ir" (nr));
130 }
131
132 /*
133  * __clear_bit_unlock - Clears a bit in memory
134  * @nr: Bit to clear
135  * @addr: Address to start counting from
136  *
137  * __clear_bit() is non-atomic and implies release semantics before the memory
138  * operation. It can be used for an unlock if no other CPUs can concurrently
139  * modify other bits in the word.
140  *
141  * No memory barrier is required here, because x86 cannot reorder stores past
142  * older loads. Same principle as spin_unlock.
143  */
144 static inline void __clear_bit_unlock(unsigned nr, volatile unsigned long *addr)
145 {
146         cmb();
147         __clear_bit(nr, addr);
148 }
149
150 #define smp_mb__before_clear_bit()      cmb()
151 #define smp_mb__after_clear_bit()       cmb()
152
153 /**
154  * __change_bit - Toggle a bit in memory
155  * @nr: the bit to change
156  * @addr: the address to start counting from
157  *
158  * Unlike change_bit(), this function is non-atomic and may be reordered.
159  * If it's called on the same region of memory simultaneously, the effect
160  * may be that only one operation succeeds.
161  */
162 static inline void __change_bit(int nr, volatile unsigned long *addr)
163 {
164         asm volatile("btc %1,%0" : ADDR : "Ir" (nr));
165 }
166
167 /**
168  * change_bit - Toggle a bit in memory
169  * @nr: Bit to change
170  * @addr: Address to start counting from
171  *
172  * change_bit() is atomic and may not be reordered.
173  * Note that @nr may be almost arbitrarily large; this function is not
174  * restricted to acting on a single-word quantity.
175  */
176 static inline void change_bit(int nr, volatile unsigned long *addr)
177 {
178         if (IS_IMMEDIATE(nr)) {
179                 asm volatile(LOCK_PREFIX "xorb %1,%0"
180                         : CONST_MASK_ADDR(nr, addr)
181                         : "iq" ((uint8_t)CONST_MASK(nr)));
182         } else {
183                 asm volatile(LOCK_PREFIX "btc %1,%0"
184                         : BITOP_ADDR(addr)
185                         : "Ir" (nr));
186         }
187 }
188
189 /**
190  * test_and_set_bit - Set a bit and return its old value
191  * @nr: Bit to set
192  * @addr: Address to count from
193  *
194  * This operation is atomic and cannot be reordered.
195  * It also implies a memory barrier.
196  */
197 static inline int test_and_set_bit(int nr, volatile unsigned long *addr)
198 {
199         int oldbit;
200
201         asm volatile(LOCK_PREFIX "bts %2,%1\n\t"
202                      "sbb %0,%0" : "=r" (oldbit), ADDR : "Ir" (nr) : "memory");
203
204         return oldbit;
205 }
206
207 /**
208  * test_and_set_bit_lock - Set a bit and return its old value for lock
209  * @nr: Bit to set
210  * @addr: Address to count from
211  *
212  * This is the same as test_and_set_bit on x86.
213  */
214 static __always_inline int
215 test_and_set_bit_lock(int nr, volatile unsigned long *addr)
216 {
217         return test_and_set_bit(nr, addr);
218 }
219
220 /**
221  * __test_and_set_bit - Set a bit and return its old value
222  * @nr: Bit to set
223  * @addr: Address to count from
224  *
225  * This operation is non-atomic and can be reordered.
226  * If two examples of this operation race, one can appear to succeed
227  * but actually fail.  You must protect multiple accesses with a lock.
228  */
229 static inline int __test_and_set_bit(int nr, volatile unsigned long *addr)
230 {
231         int oldbit;
232
233         asm("bts %2,%1\n\t"
234             "sbb %0,%0"
235             : "=r" (oldbit), ADDR
236             : "Ir" (nr));
237         return oldbit;
238 }
239
240 /**
241  * test_and_clear_bit - Clear a bit and return its old value
242  * @nr: Bit to clear
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_clear_bit(int nr, volatile unsigned long *addr)
249 {
250         int oldbit;
251
252         asm volatile(LOCK_PREFIX "btr %2,%1\n\t"
253                      "sbb %0,%0"
254                      : "=r" (oldbit), ADDR : "Ir" (nr) : "memory");
255
256         return oldbit;
257 }
258
259 /**
260  * __test_and_clear_bit - Clear a bit and return its old value
261  * @nr: Bit to clear
262  * @addr: Address to count from
263  *
264  * This operation is non-atomic and can be reordered.
265  * If two examples of this operation race, one can appear to succeed
266  * but actually fail.  You must protect multiple accesses with a lock.
267  *
268  * Note: the operation is performed atomically with respect to
269  * the local CPU, but not other CPUs. Portable code should not
270  * rely on this behaviour.
271  * KVM relies on this behaviour on x86 for modifying memory that is also
272  * accessed from a hypervisor on the same CPU if running in a VM: don't change
273  * this without also updating arch/x86/kernel/kvm.c
274  */
275 static inline int __test_and_clear_bit(int nr, volatile unsigned long *addr)
276 {
277         int oldbit;
278
279         asm volatile("btr %2,%1\n\t"
280                      "sbb %0,%0"
281                      : "=r" (oldbit), ADDR
282                      : "Ir" (nr));
283         return oldbit;
284 }
285
286 /* WARNING: non atomic and it can be reordered! */
287 static inline int __test_and_change_bit(int nr, volatile unsigned long *addr)
288 {
289         int oldbit;
290
291         asm volatile("btc %2,%1\n\t"
292                      "sbb %0,%0"
293                      : "=r" (oldbit), ADDR
294                      : "Ir" (nr) : "memory");
295
296         return oldbit;
297 }
298
299 /**
300  * test_and_change_bit - Change a bit and return its old value
301  * @nr: Bit to change
302  * @addr: Address to count from
303  *
304  * This operation is atomic and cannot be reordered.
305  * It also implies a memory barrier.
306  */
307 static inline int test_and_change_bit(int nr, volatile unsigned long *addr)
308 {
309         int oldbit;
310
311         asm volatile(LOCK_PREFIX "btc %2,%1\n\t"
312                      "sbb %0,%0"
313                      : "=r" (oldbit), ADDR : "Ir" (nr) : "memory");
314
315         return oldbit;
316 }
317
318 static __always_inline int constant_test_bit(unsigned int nr, const volatile unsigned long *addr)
319 {
320         return ((1UL << (nr % BITS_PER_LONG)) &
321                 (addr[nr / BITS_PER_LONG])) != 0;
322 }
323
324 static inline int variable_test_bit(int nr, volatile const unsigned long *addr)
325 {
326         int oldbit;
327
328         asm volatile("bt %2,%1\n\t"
329                      "sbb %0,%0"
330                      : "=r" (oldbit)
331                      : "m" (*(unsigned long *)addr), "Ir" (nr));
332
333         return oldbit;
334 }
335
336 #define test_bit(nr, addr)                      \
337         (__builtin_constant_p((nr))             \
338          ? constant_test_bit((nr), (addr))      \
339          : variable_test_bit((nr), (addr)))
340 /**
341  * __ffs - find first set bit in word
342  * @word: The word to search
343  *
344  * Undefined if no bit exists, so code should check against 0 first.
345  */
346 static inline unsigned long __ffs(unsigned long word)
347 {
348         asm("rep; bsf %1,%0"
349                 : "=r" (word)
350                 : "rm" (word));
351         return word;
352 }
353
354 /**
355  * ffz - find first zero bit in word
356  * @word: The word to search
357  *
358  * Undefined if no zero exists, so code should check against ~0UL first.
359  */
360 static inline unsigned long ffz(unsigned long word)
361 {
362         asm("rep; bsf %1,%0"
363                 : "=r" (word)
364                 : "r" (~word));
365         return word;
366 }
367
368 /*
369  * __fls: find last set bit in word
370  * @word: The word to search
371  *
372  * Undefined if no set bit exists, so code should check against 0 first.
373  */
374 static inline unsigned long __fls(unsigned long word)
375 {
376         asm("bsr %1,%0"
377             : "=r" (word)
378             : "rm" (word));
379         return word;
380 }
381
382 #undef ADDR
383
384 /**
385  * ffs - find first set bit in word
386  * @x: the word to search
387  *
388  * This is defined the same way as the libc and compiler builtin ffs
389  * routines, therefore differs in spirit from the other bitops.
390  *
391  * ffs(value) returns 0 if value is 0 or the position of the first
392  * set bit if value is nonzero. The first (least significant) bit
393  * is at position 1.
394  */
395 static inline int ffs(int x)
396 {
397         int r;
398
399 #ifdef CONFIG_X86_64
400         /*
401          * AMD64 says BSFL won't clobber the dest reg if x==0; Intel64 says the
402          * dest reg is undefined if x==0, but their CPU architect says its
403          * value is written to set it to the same as before, except that the
404          * top 32 bits will be cleared.
405          *
406          * We cannot do this on 32 bits because at the very least some
407          * 486 CPUs did not behave this way.
408          */
409         asm("bsfl %1,%0"
410             : "=r" (r)
411             : "rm" (x), "0" (-1));
412 #elif defined(CONFIG_X86_CMOV)
413         asm("bsfl %1,%0\n\t"
414             "cmovzl %2,%0"
415             : "=&r" (r) : "rm" (x), "r" (-1));
416 #else
417         asm("bsfl %1,%0\n\t"
418             "jnz 1f\n\t"
419             "movl $-1,%0\n"
420             "1:" : "=r" (r) : "rm" (x));
421 #endif
422         return r + 1;
423 }
424
425 /**
426  * fls - find last set bit in word
427  * @x: the word to search
428  *
429  * This is defined in a similar way as the libc and compiler builtin
430  * ffs, but returns the position of the most significant set bit.
431  *
432  * fls(value) returns 0 if value is 0 or the position of the last
433  * set bit if value is nonzero. The last (most significant) bit is
434  * at position 32.
435  */
436 static inline int fls(int x)
437 {
438         int r;
439
440 #ifdef CONFIG_X86_64
441         /*
442          * AMD64 says BSRL won't clobber the dest reg if x==0; Intel64 says the
443          * dest reg is undefined if x==0, but their CPU architect says its
444          * value is written to set it to the same as before, except that the
445          * top 32 bits will be cleared.
446          *
447          * We cannot do this on 32 bits because at the very least some
448          * 486 CPUs did not behave this way.
449          */
450         asm("bsrl %1,%0"
451             : "=r" (r)
452             : "rm" (x), "0" (-1));
453 #elif defined(CONFIG_X86_CMOV)
454         asm("bsrl %1,%0\n\t"
455             "cmovzl %2,%0"
456             : "=&r" (r) : "rm" (x), "rm" (-1));
457 #else
458         asm("bsrl %1,%0\n\t"
459             "jnz 1f\n\t"
460             "movl $-1,%0\n"
461             "1:" : "=r" (r) : "rm" (x));
462 #endif
463         return r + 1;
464 }
465
466 /**
467  * fls64 - find last set bit in a 64-bit word
468  * @x: the word to search
469  *
470  * This is defined in a similar way as the libc and compiler builtin
471  * ffsll, but returns the position of the most significant set bit.
472  *
473  * fls64(value) returns 0 if value is 0 or the position of the last
474  * set bit if value is nonzero. The last (most significant) bit is
475  * at position 64.
476  */
477 #ifdef CONFIG_X86_64
478 static __always_inline int fls64(uint64_t x)
479 {
480         int bitpos = -1;
481         /*
482          * AMD64 says BSRQ won't clobber the dest reg if x==0; Intel64 says the
483          * dest reg is undefined if x==0, but their CPU architect says its
484          * value is written to set it to the same as before.
485          */
486         asm("bsrq %1,%q0"
487             : "+r" (bitpos)
488             : "rm" (x));
489         return bitpos + 1;
490 }
491 #else
492 #error "Need the generic version of fls64"
493 #endif
494 #endif /* _ASM_X86_BITOPS_H */