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