move whether atomic byte/short exists to uatomic_arch_*.h
[urcu.git] / tests / api_ppc.h
1 /* MECHANICALLY GENERATED, DO NOT EDIT!!! */
2
3 #ifndef _INCLUDE_API_H
4 #define _INCLUDE_API_H
5
6 /*
7 * common.h: Common Linux kernel-isms.
8 *
9 * This program is free software; you can redistribute it and/or modify
10 * it under the terms of the GNU General Public License as published by
11 * the Free Software Foundation; but version 2 of the License only due
12 * to code included from the Linux kernel.
13 *
14 * This program is distributed in the hope that it will be useful,
15 * but WITHOUT ANY WARRANTY; without even the implied warranty of
16 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 * GNU General Public License for more details.
18 *
19 * You should have received a copy of the GNU General Public License
20 * along with this program; if not, write to the Free Software
21 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
22 *
23 * Copyright (c) 2006 Paul E. McKenney, IBM.
24 *
25 * Much code taken from the Linux kernel. For such code, the option
26 * to redistribute under later versions of GPL might not be available.
27 */
28
29 #include <urcu/arch.h>
30
31 #ifndef __always_inline
32 #define __always_inline inline
33 #endif
34
35 #define BUILD_BUG_ON(condition) ((void)sizeof(char[1 - 2*!!(condition)]))
36 #define BUILD_BUG_ON_ZERO(e) (sizeof(char[1 - 2 * !!(e)]) - 1)
37
38 #ifdef __ASSEMBLY__
39 # define stringify_in_c(...) __VA_ARGS__
40 # define ASM_CONST(x) x
41 #else
42 /* This version of stringify will deal with commas... */
43 # define __stringify_in_c(...) #__VA_ARGS__
44 # define stringify_in_c(...) __stringify_in_c(__VA_ARGS__) " "
45 # define __ASM_CONST(x) x##UL
46 # define ASM_CONST(x) __ASM_CONST(x)
47 #endif
48
49
50 /*
51 * arch-ppc64.h: Expose PowerPC atomic instructions.
52 *
53 * This program is free software; you can redistribute it and/or modify
54 * it under the terms of the GNU General Public License as published by
55 * the Free Software Foundation; but version 2 of the License only due
56 * to code included from the Linux kernel.
57 *
58 * This program is distributed in the hope that it will be useful,
59 * but WITHOUT ANY WARRANTY; without even the implied warranty of
60 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
61 * GNU General Public License for more details.
62 *
63 * You should have received a copy of the GNU General Public License
64 * along with this program; if not, write to the Free Software
65 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
66 *
67 * Copyright (c) 2006 Paul E. McKenney, IBM.
68 *
69 * Much code taken from the Linux kernel. For such code, the option
70 * to redistribute under later versions of GPL might not be available.
71 */
72
73 /*
74 * Machine parameters.
75 */
76
77 #define CONFIG_PPC64
78
79 /*#define CACHE_LINE_SIZE 128 */
80 #define ____cacheline_internodealigned_in_smp \
81 __attribute__((__aligned__(1 << 7)))
82
83 #if 0 /* duplicate with arch_atomic.h */
84
85 /*
86 * Atomic data structure, initialization, and access.
87 */
88
89 typedef struct { volatile int counter; } atomic_t;
90
91 #define ATOMIC_INIT(i) { (i) }
92
93 #define atomic_read(v) ((v)->counter)
94 #define atomic_set(v, i) (((v)->counter) = (i))
95
96 /*
97 * Atomic operations.
98 */
99
100 #define LWSYNC lwsync
101 #define PPC405_ERR77(ra,rb)
102 #ifdef CONFIG_SMP
103 # define LWSYNC_ON_SMP stringify_in_c(LWSYNC) "\n"
104 # define ISYNC_ON_SMP "\n\tisync\n"
105 #else
106 # define LWSYNC_ON_SMP
107 # define ISYNC_ON_SMP
108 #endif
109
110 /*
111 * Atomic exchange
112 *
113 * Changes the memory location '*ptr' to be val and returns
114 * the previous value stored there.
115 */
116 static __always_inline unsigned long
117 __xchg_u32(volatile void *p, unsigned long val)
118 {
119 unsigned long prev;
120
121 __asm__ __volatile__(
122 LWSYNC_ON_SMP
123 "1: lwarx %0,0,%2 \n"
124 PPC405_ERR77(0,%2)
125 " stwcx. %3,0,%2 \n\
126 bne- 1b"
127 ISYNC_ON_SMP
128 : "=&r" (prev), "+m" (*(volatile unsigned int *)p)
129 : "r" (p), "r" (val)
130 : "cc", "memory");
131
132 return prev;
133 }
134
135 /*
136 * Atomic exchange
137 *
138 * Changes the memory location '*ptr' to be val and returns
139 * the previous value stored there.
140 */
141 static __always_inline unsigned long
142 __xchg_u32_local(volatile void *p, unsigned long val)
143 {
144 unsigned long prev;
145
146 __asm__ __volatile__(
147 "1: lwarx %0,0,%2 \n"
148 PPC405_ERR77(0,%2)
149 " stwcx. %3,0,%2 \n\
150 bne- 1b"
151 : "=&r" (prev), "+m" (*(volatile unsigned int *)p)
152 : "r" (p), "r" (val)
153 : "cc", "memory");
154
155 return prev;
156 }
157
158 #ifdef CONFIG_PPC64
159 static __always_inline unsigned long
160 __xchg_u64(volatile void *p, unsigned long val)
161 {
162 unsigned long prev;
163
164 __asm__ __volatile__(
165 LWSYNC_ON_SMP
166 "1: ldarx %0,0,%2 \n"
167 PPC405_ERR77(0,%2)
168 " stdcx. %3,0,%2 \n\
169 bne- 1b"
170 ISYNC_ON_SMP
171 : "=&r" (prev), "+m" (*(volatile unsigned long *)p)
172 : "r" (p), "r" (val)
173 : "cc", "memory");
174
175 return prev;
176 }
177
178 static __always_inline unsigned long
179 __xchg_u64_local(volatile void *p, unsigned long val)
180 {
181 unsigned long prev;
182
183 __asm__ __volatile__(
184 "1: ldarx %0,0,%2 \n"
185 PPC405_ERR77(0,%2)
186 " stdcx. %3,0,%2 \n\
187 bne- 1b"
188 : "=&r" (prev), "+m" (*(volatile unsigned long *)p)
189 : "r" (p), "r" (val)
190 : "cc", "memory");
191
192 return prev;
193 }
194 #endif
195
196 /*
197 * This function doesn't exist, so you'll get a linker error
198 * if something tries to do an invalid xchg().
199 */
200 extern void __xchg_called_with_bad_pointer(void);
201
202 static __always_inline unsigned long
203 __xchg(volatile void *ptr, unsigned long x, unsigned int size)
204 {
205 switch (size) {
206 case 4:
207 return __xchg_u32(ptr, x);
208 #ifdef CONFIG_PPC64
209 case 8:
210 return __xchg_u64(ptr, x);
211 #endif
212 }
213 __xchg_called_with_bad_pointer();
214 return x;
215 }
216
217 static __always_inline unsigned long
218 __xchg_local(volatile void *ptr, unsigned long x, unsigned int size)
219 {
220 switch (size) {
221 case 4:
222 return __xchg_u32_local(ptr, x);
223 #ifdef CONFIG_PPC64
224 case 8:
225 return __xchg_u64_local(ptr, x);
226 #endif
227 }
228 __xchg_called_with_bad_pointer();
229 return x;
230 }
231 #define xchg(ptr,x) \
232 ({ \
233 __typeof__(*(ptr)) _x_ = (x); \
234 (__typeof__(*(ptr))) __xchg((ptr), (unsigned long)_x_, sizeof(*(ptr))); \
235 })
236
237 #define xchg_local(ptr,x) \
238 ({ \
239 __typeof__(*(ptr)) _x_ = (x); \
240 (__typeof__(*(ptr))) __xchg_local((ptr), \
241 (unsigned long)_x_, sizeof(*(ptr))); \
242 })
243
244 /*
245 * Compare and exchange - if *p == old, set it to new,
246 * and return the old value of *p.
247 */
248 #define __HAVE_ARCH_CMPXCHG 1
249
250 static __always_inline unsigned long
251 __cmpxchg_u32(volatile unsigned int *p, unsigned long old, unsigned long new)
252 {
253 unsigned int prev;
254
255 __asm__ __volatile__ (
256 LWSYNC_ON_SMP
257 "1: lwarx %0,0,%2 # __cmpxchg_u32\n\
258 cmpw 0,%0,%3\n\
259 bne- 2f\n"
260 PPC405_ERR77(0,%2)
261 " stwcx. %4,0,%2\n\
262 bne- 1b"
263 ISYNC_ON_SMP
264 "\n\
265 2:"
266 : "=&r" (prev), "+m" (*p)
267 : "r" (p), "r" (old), "r" (new)
268 : "cc", "memory");
269
270 return prev;
271 }
272
273 static __always_inline unsigned long
274 __cmpxchg_u32_local(volatile unsigned int *p, unsigned long old,
275 unsigned long new)
276 {
277 unsigned int prev;
278
279 __asm__ __volatile__ (
280 "1: lwarx %0,0,%2 # __cmpxchg_u32\n\
281 cmpw 0,%0,%3\n\
282 bne- 2f\n"
283 PPC405_ERR77(0,%2)
284 " stwcx. %4,0,%2\n\
285 bne- 1b"
286 "\n\
287 2:"
288 : "=&r" (prev), "+m" (*p)
289 : "r" (p), "r" (old), "r" (new)
290 : "cc", "memory");
291
292 return prev;
293 }
294
295 #ifdef CONFIG_PPC64
296 static __always_inline unsigned long
297 __cmpxchg_u64(volatile unsigned long *p, unsigned long old, unsigned long new)
298 {
299 unsigned long prev;
300
301 __asm__ __volatile__ (
302 LWSYNC_ON_SMP
303 "1: ldarx %0,0,%2 # __cmpxchg_u64\n\
304 cmpd 0,%0,%3\n\
305 bne- 2f\n\
306 stdcx. %4,0,%2\n\
307 bne- 1b"
308 ISYNC_ON_SMP
309 "\n\
310 2:"
311 : "=&r" (prev), "+m" (*p)
312 : "r" (p), "r" (old), "r" (new)
313 : "cc", "memory");
314
315 return prev;
316 }
317
318 static __always_inline unsigned long
319 __cmpxchg_u64_local(volatile unsigned long *p, unsigned long old,
320 unsigned long new)
321 {
322 unsigned long prev;
323
324 __asm__ __volatile__ (
325 "1: ldarx %0,0,%2 # __cmpxchg_u64\n\
326 cmpd 0,%0,%3\n\
327 bne- 2f\n\
328 stdcx. %4,0,%2\n\
329 bne- 1b"
330 "\n\
331 2:"
332 : "=&r" (prev), "+m" (*p)
333 : "r" (p), "r" (old), "r" (new)
334 : "cc", "memory");
335
336 return prev;
337 }
338 #endif
339
340 /* This function doesn't exist, so you'll get a linker error
341 if something tries to do an invalid cmpxchg(). */
342 extern void __cmpxchg_called_with_bad_pointer(void);
343
344 static __always_inline unsigned long
345 __cmpxchg(volatile void *ptr, unsigned long old, unsigned long new,
346 unsigned int size)
347 {
348 switch (size) {
349 case 4:
350 return __cmpxchg_u32(ptr, old, new);
351 #ifdef CONFIG_PPC64
352 case 8:
353 return __cmpxchg_u64(ptr, old, new);
354 #endif
355 }
356 __cmpxchg_called_with_bad_pointer();
357 return old;
358 }
359
360 static __always_inline unsigned long
361 __cmpxchg_local(volatile void *ptr, unsigned long old, unsigned long new,
362 unsigned int size)
363 {
364 switch (size) {
365 case 4:
366 return __cmpxchg_u32_local(ptr, old, new);
367 #ifdef CONFIG_PPC64
368 case 8:
369 return __cmpxchg_u64_local(ptr, old, new);
370 #endif
371 }
372 __cmpxchg_called_with_bad_pointer();
373 return old;
374 }
375
376 #define cmpxchg(ptr, o, n) \
377 ({ \
378 __typeof__(*(ptr)) _o_ = (o); \
379 __typeof__(*(ptr)) _n_ = (n); \
380 (__typeof__(*(ptr))) __cmpxchg((ptr), (unsigned long)_o_, \
381 (unsigned long)_n_, sizeof(*(ptr))); \
382 })
383
384
385 #define cmpxchg_local(ptr, o, n) \
386 ({ \
387 __typeof__(*(ptr)) _o_ = (o); \
388 __typeof__(*(ptr)) _n_ = (n); \
389 (__typeof__(*(ptr))) __cmpxchg_local((ptr), (unsigned long)_o_, \
390 (unsigned long)_n_, sizeof(*(ptr))); \
391 })
392
393 #ifdef CONFIG_PPC64
394 /*
395 * We handle most unaligned accesses in hardware. On the other hand
396 * unaligned DMA can be very expensive on some ppc64 IO chips (it does
397 * powers of 2 writes until it reaches sufficient alignment).
398 *
399 * Based on this we disable the IP header alignment in network drivers.
400 * We also modify NET_SKB_PAD to be a cacheline in size, thus maintaining
401 * cacheline alignment of buffers.
402 */
403 #define NET_IP_ALIGN 0
404 #define NET_SKB_PAD L1_CACHE_BYTES
405
406 #define cmpxchg64(ptr, o, n) \
407 ({ \
408 BUILD_BUG_ON(sizeof(*(ptr)) != 8); \
409 cmpxchg((ptr), (o), (n)); \
410 })
411 #define cmpxchg64_local(ptr, o, n) \
412 ({ \
413 BUILD_BUG_ON(sizeof(*(ptr)) != 8); \
414 cmpxchg_local((ptr), (o), (n)); \
415 })
416 #endif
417
418 #define atomic_cmpxchg(v, o, n) (cmpxchg(&((v)->counter), (o), (n)))
419 #define atomic_xchg(v, new) (xchg(&((v)->counter), new))
420
421 /**
422 * atomic_add - add integer to atomic variable
423 * @i: integer value to add
424 * @v: pointer of type atomic_t
425 *
426 * Atomically adds @a to @v.
427 */
428 static __inline__ void atomic_add(int a, atomic_t *v)
429 {
430 int t;
431
432 __asm__ __volatile__(
433 "1: lwarx %0,0,%3 # atomic_add\n\
434 add %0,%2,%0 \n\
435 stwcx. %0,0,%3 \n\
436 bne- 1b"
437 : "=&r" (t), "+m" (v->counter)
438 : "r" (a), "r" (&v->counter)
439 : "cc");
440 }
441
442 /**
443 * atomic_sub - subtract the atomic variable
444 * @i: integer value to subtract
445 * @v: pointer of type atomic_t
446 *
447 * Atomically subtracts @a from @v.
448 */
449 static __inline__ void atomic_sub(int a, atomic_t *v)
450 {
451 int t;
452
453 __asm__ __volatile__(
454 "1: lwarx %0,0,%3 # atomic_sub \n\
455 subf %0,%2,%0 \n\
456 stwcx. %0,0,%3 \n\
457 bne- 1b"
458 : "=&r" (t), "+m" (v->counter)
459 : "r" (a), "r" (&v->counter)
460 : "cc");
461 }
462
463 static __inline__ atomic_sub_return(int a, atomic_t *v)
464 {
465 int t;
466
467 __asm__ __volatile__(
468 "lwsync\n\
469 1: lwarx %0,0,%2 # atomic_sub_return\n\
470 subf %0,%1,%0\n\
471 stwcx. %0,0,%2 \n\
472 bne- 1b \n\
473 isync"
474 : "=&r" (t)
475 : "r" (a), "r" (&v->counter)
476 : "cc", "memory");
477
478 return t;
479 }
480
481 /**
482 * atomic_sub_and_test - subtract value from variable and test result
483 * @i: integer value to subtract
484 * @v: pointer of type atomic_t
485 *
486 * Atomically subtracts @i from @v and returns
487 * true if the result is zero, or false for all
488 * other cases.
489 */
490 static __inline__ int atomic_sub_and_test(int a, atomic_t *v)
491 {
492 return atomic_sub_return(a, v) == 0;
493 }
494
495 /**
496 * atomic_inc - increment atomic variable
497 * @v: pointer of type atomic_t
498 *
499 * Atomically increments @v by 1.
500 */
501 static __inline__ void atomic_inc(atomic_t *v)
502 {
503 atomic_add(1, v);
504 }
505
506 /**
507 * atomic_dec - decrement atomic variable
508 * @v: pointer of type atomic_t
509 *
510 * Atomically decrements @v by 1.
511 */
512 static __inline__ void atomic_dec(atomic_t *v)
513 {
514 atomic_sub(1, v);
515 }
516
517 /**
518 * atomic_dec_and_test - decrement and test
519 * @v: pointer of type atomic_t
520 *
521 * Atomically decrements @v by 1 and
522 * returns true if the result is 0, or false for all other
523 * cases.
524 */
525 static __inline__ int atomic_dec_and_test(atomic_t *v)
526 {
527 return atomic_sub_and_test(1, v);
528 }
529
530 /**
531 * atomic_inc_and_test - increment and test
532 * @v: pointer of type atomic_t
533 *
534 * Atomically increments @v by 1
535 * and returns true if the result is zero, or false for all
536 * other cases.
537 */
538 static __inline__ int atomic_inc_and_test(atomic_t *v)
539 {
540 return atomic_inc_return(v);
541 }
542
543 /**
544 * atomic_add_return - add and return
545 * @v: pointer of type atomic_t
546 * @i: integer value to add
547 *
548 * Atomically adds @i to @v and returns @i + @v
549 */
550 static __inline__ int atomic_add_return(int a, atomic_t *v)
551 {
552 int t;
553
554 __asm__ __volatile__(
555 "lwsync \n\
556 1: lwarx %0,0,%2 # atomic_add_return \n\
557 add %0,%1,%0 \n\
558 stwcx. %0,0,%2 \n\
559 bne- 1b \n\
560 isync"
561 : "=&r" (t)
562 : "r" (a), "r" (&v->counter)
563 : "cc", "memory");
564
565 return t;
566 }
567
568 /**
569 * atomic_add_negative - add and test if negative
570 * @v: pointer of type atomic_t
571 * @i: integer value to add
572 *
573 * Atomically adds @i to @v and returns true
574 * if the result is negative, or false when
575 * result is greater than or equal to zero.
576 */
577 static __inline__ int atomic_add_negative(int a, atomic_t *v)
578 {
579 return atomic_add_return(a, v) < 0;
580 }
581
582 /**
583 * atomic_add_unless - add unless the number is a given value
584 * @v: pointer of type atomic_t
585 * @a: the amount to add to v...
586 * @u: ...unless v is equal to u.
587 *
588 * Atomically adds @a to @v, so long as it was not @u.
589 * Returns non-zero if @v was not @u, and zero otherwise.
590 */
591 static __inline__ int atomic_add_unless(atomic_t *v, int a, int u)
592 {
593 int t;
594
595 __asm__ __volatile__(
596 "lwsync \n\
597 1: lwarx %0,0,%1 # atomic_add_unless\n\
598 cmpd 0,%0,%3 \n\
599 beq- 2f \n\
600 add %0,%2,%0 \n\
601 stwcx. %0,0,%1 \n\
602 bne- 1b \n\
603 isync \n\
604 subf %0,%2,%0 \n\
605 2:"
606 : "=&r" (t)
607 : "r" (&v->counter), "r" (a), "r" (u)
608 : "cc", "memory");
609
610 return t != u;
611 }
612
613 #define atomic_inc_not_zero(v) atomic_add_unless((v), 1, 0)
614
615 #define atomic_inc_return(v) (atomic_add_return(1,v))
616 #define atomic_dec_return(v) (atomic_sub_return(1,v))
617
618 /* Atomic operations are already serializing on x86 */
619 #define smp_mb__before_atomic_dec() smp_mb()
620 #define smp_mb__after_atomic_dec() smp_mb()
621 #define smp_mb__before_atomic_inc() smp_mb()
622 #define smp_mb__after_atomic_inc() smp_mb()
623
624 #endif //0 /* duplicate with arch_atomic.h */
625
626 /*
627 * api_pthreads.h: API mapping to pthreads environment.
628 *
629 * This program is free software; you can redistribute it and/or modify
630 * it under the terms of the GNU General Public License as published by
631 * the Free Software Foundation; either version 2 of the License, or
632 * (at your option) any later version. However, please note that much
633 * of the code in this file derives from the Linux kernel, and that such
634 * code may not be available except under GPLv2.
635 *
636 * This program is distributed in the hope that it will be useful,
637 * but WITHOUT ANY WARRANTY; without even the implied warranty of
638 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
639 * GNU General Public License for more details.
640 *
641 * You should have received a copy of the GNU General Public License
642 * along with this program; if not, write to the Free Software
643 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
644 *
645 * Copyright (c) 2006 Paul E. McKenney, IBM.
646 */
647
648 #include <stdio.h>
649 #include <stdlib.h>
650 #include <errno.h>
651 #include <limits.h>
652 #include <sys/types.h>
653 #define __USE_GNU
654 #include <pthread.h>
655 #include <sched.h>
656 #include <sys/param.h>
657 /* #include "atomic.h" */
658
659 /*
660 * Compiler magic.
661 */
662 #define container_of(ptr, type, member) ({ \
663 const typeof( ((type *)0)->member ) *__mptr = (ptr); \
664 (type *)( (char *)__mptr - offsetof(type,member) );})
665
666 /*
667 * Default machine parameters.
668 */
669
670 #ifndef CACHE_LINE_SIZE
671 /* #define CACHE_LINE_SIZE 128 */
672 #endif /* #ifndef CACHE_LINE_SIZE */
673
674 /*
675 * Exclusive locking primitives.
676 */
677
678 typedef pthread_mutex_t spinlock_t;
679
680 #define DEFINE_SPINLOCK(lock) spinlock_t lock = PTHREAD_MUTEX_INITIALIZER;
681 #define __SPIN_LOCK_UNLOCKED(lockp) PTHREAD_MUTEX_INITIALIZER
682
683 static void spin_lock_init(spinlock_t *sp)
684 {
685 if (pthread_mutex_init(sp, NULL) != 0) {
686 perror("spin_lock_init:pthread_mutex_init");
687 exit(-1);
688 }
689 }
690
691 static void spin_lock(spinlock_t *sp)
692 {
693 if (pthread_mutex_lock(sp) != 0) {
694 perror("spin_lock:pthread_mutex_lock");
695 exit(-1);
696 }
697 }
698
699 static void spin_unlock(spinlock_t *sp)
700 {
701 if (pthread_mutex_unlock(sp) != 0) {
702 perror("spin_unlock:pthread_mutex_unlock");
703 exit(-1);
704 }
705 }
706
707 #define spin_lock_irqsave(l, f) do { f = 1; spin_lock(l); } while (0)
708 #define spin_unlock_irqrestore(l, f) do { f = 0; spin_unlock(l); } while (0)
709
710 /*
711 * Thread creation/destruction primitives.
712 */
713
714 typedef pthread_t thread_id_t;
715
716 #define NR_THREADS 128
717
718 #define __THREAD_ID_MAP_EMPTY 0
719 #define __THREAD_ID_MAP_WAITING 1
720 thread_id_t __thread_id_map[NR_THREADS];
721 spinlock_t __thread_id_map_mutex;
722
723 #define for_each_thread(t) \
724 for (t = 0; t < NR_THREADS; t++)
725
726 #define for_each_running_thread(t) \
727 for (t = 0; t < NR_THREADS; t++) \
728 if ((__thread_id_map[t] != __THREAD_ID_MAP_EMPTY) && \
729 (__thread_id_map[t] != __THREAD_ID_MAP_WAITING))
730
731 #define for_each_tid(t, tid) \
732 for (t = 0; t < NR_THREADS; t++) \
733 if ((((tid) = __thread_id_map[t]) != __THREAD_ID_MAP_EMPTY) && \
734 ((tid) != __THREAD_ID_MAP_WAITING))
735
736 pthread_key_t thread_id_key;
737
738 static int __smp_thread_id(void)
739 {
740 int i;
741 thread_id_t tid = pthread_self();
742
743 for (i = 0; i < NR_THREADS; i++) {
744 if (__thread_id_map[i] == tid) {
745 long v = i + 1; /* must be non-NULL. */
746
747 if (pthread_setspecific(thread_id_key, (void *)v) != 0) {
748 perror("pthread_setspecific");
749 exit(-1);
750 }
751 return i;
752 }
753 }
754 spin_lock(&__thread_id_map_mutex);
755 for (i = 0; i < NR_THREADS; i++) {
756 if (__thread_id_map[i] == tid)
757 spin_unlock(&__thread_id_map_mutex);
758 return i;
759 }
760 spin_unlock(&__thread_id_map_mutex);
761 fprintf(stderr, "smp_thread_id: Rogue thread, id: %d(%#x)\n",
762 (int)tid, (int)tid);
763 exit(-1);
764 }
765
766 static int smp_thread_id(void)
767 {
768 void *id;
769
770 id = pthread_getspecific(thread_id_key);
771 if (id == NULL)
772 return __smp_thread_id();
773 return (long)(id - 1);
774 }
775
776 static thread_id_t create_thread(void *(*func)(void *), void *arg)
777 {
778 thread_id_t tid;
779 int i;
780
781 spin_lock(&__thread_id_map_mutex);
782 for (i = 0; i < NR_THREADS; i++) {
783 if (__thread_id_map[i] == __THREAD_ID_MAP_EMPTY)
784 break;
785 }
786 if (i >= NR_THREADS) {
787 spin_unlock(&__thread_id_map_mutex);
788 fprintf(stderr, "Thread limit of %d exceeded!\n", NR_THREADS);
789 exit(-1);
790 }
791 __thread_id_map[i] = __THREAD_ID_MAP_WAITING;
792 spin_unlock(&__thread_id_map_mutex);
793 if (pthread_create(&tid, NULL, func, arg) != 0) {
794 perror("create_thread:pthread_create");
795 exit(-1);
796 }
797 __thread_id_map[i] = tid;
798 return tid;
799 }
800
801 static void *wait_thread(thread_id_t tid)
802 {
803 int i;
804 void *vp;
805
806 for (i = 0; i < NR_THREADS; i++) {
807 if (__thread_id_map[i] == tid)
808 break;
809 }
810 if (i >= NR_THREADS){
811 fprintf(stderr, "wait_thread: bad tid = %d(%#x)\n",
812 (int)tid, (int)tid);
813 exit(-1);
814 }
815 if (pthread_join(tid, &vp) != 0) {
816 perror("wait_thread:pthread_join");
817 exit(-1);
818 }
819 __thread_id_map[i] = __THREAD_ID_MAP_EMPTY;
820 return vp;
821 }
822
823 static void wait_all_threads(void)
824 {
825 int i;
826 thread_id_t tid;
827
828 for (i = 1; i < NR_THREADS; i++) {
829 tid = __thread_id_map[i];
830 if (tid != __THREAD_ID_MAP_EMPTY &&
831 tid != __THREAD_ID_MAP_WAITING)
832 (void)wait_thread(tid);
833 }
834 }
835
836 static void run_on(int cpu)
837 {
838 cpu_set_t mask;
839
840 CPU_ZERO(&mask);
841 CPU_SET(cpu, &mask);
842 sched_setaffinity(0, sizeof(mask), &mask);
843 }
844
845 /*
846 * timekeeping -- very crude -- should use MONOTONIC...
847 */
848
849 long long get_microseconds(void)
850 {
851 struct timeval tv;
852
853 if (gettimeofday(&tv, NULL) != 0)
854 abort();
855 return ((long long)tv.tv_sec) * 1000000LL + (long long)tv.tv_usec;
856 }
857
858 /*
859 * Per-thread variables.
860 */
861
862 #define DEFINE_PER_THREAD(type, name) \
863 struct { \
864 __typeof__(type) v \
865 __attribute__((__aligned__(CACHE_LINE_SIZE))); \
866 } __per_thread_##name[NR_THREADS];
867 #define DECLARE_PER_THREAD(type, name) extern DEFINE_PER_THREAD(type, name)
868
869 #define per_thread(name, thread) __per_thread_##name[thread].v
870 #define __get_thread_var(name) per_thread(name, smp_thread_id())
871
872 #define init_per_thread(name, v) \
873 do { \
874 int __i_p_t_i; \
875 for (__i_p_t_i = 0; __i_p_t_i < NR_THREADS; __i_p_t_i++) \
876 per_thread(name, __i_p_t_i) = v; \
877 } while (0)
878
879 /*
880 * CPU traversal primitives.
881 */
882
883 #ifndef NR_CPUS
884 #define NR_CPUS 16
885 #endif /* #ifndef NR_CPUS */
886
887 #define for_each_possible_cpu(cpu) \
888 for (cpu = 0; cpu < NR_CPUS; cpu++)
889 #define for_each_online_cpu(cpu) \
890 for (cpu = 0; cpu < NR_CPUS; cpu++)
891
892 /*
893 * Per-CPU variables.
894 */
895
896 #define DEFINE_PER_CPU(type, name) \
897 struct { \
898 __typeof__(type) v \
899 __attribute__((__aligned__(CACHE_LINE_SIZE))); \
900 } __per_cpu_##name[NR_CPUS]
901 #define DECLARE_PER_CPU(type, name) extern DEFINE_PER_CPU(type, name)
902
903 DEFINE_PER_THREAD(int, smp_processor_id);
904
905 #define per_cpu(name, thread) __per_cpu_##name[thread].v
906 #define __get_cpu_var(name) per_cpu(name, smp_processor_id())
907
908 #define init_per_cpu(name, v) \
909 do { \
910 int __i_p_c_i; \
911 for (__i_p_c_i = 0; __i_p_c_i < NR_CPUS; __i_p_c_i++) \
912 per_cpu(name, __i_p_c_i) = v; \
913 } while (0)
914
915 /*
916 * CPU state checking (crowbarred).
917 */
918
919 #define idle_cpu(cpu) 0
920 #define in_softirq() 1
921 #define hardirq_count() 0
922 #define PREEMPT_SHIFT 0
923 #define SOFTIRQ_SHIFT (PREEMPT_SHIFT + PREEMPT_BITS)
924 #define HARDIRQ_SHIFT (SOFTIRQ_SHIFT + SOFTIRQ_BITS)
925 #define PREEMPT_BITS 8
926 #define SOFTIRQ_BITS 8
927
928 /*
929 * CPU hotplug.
930 */
931
932 struct notifier_block {
933 int (*notifier_call)(struct notifier_block *, unsigned long, void *);
934 struct notifier_block *next;
935 int priority;
936 };
937
938 #define CPU_ONLINE 0x0002 /* CPU (unsigned)v is up */
939 #define CPU_UP_PREPARE 0x0003 /* CPU (unsigned)v coming up */
940 #define CPU_UP_CANCELED 0x0004 /* CPU (unsigned)v NOT coming up */
941 #define CPU_DOWN_PREPARE 0x0005 /* CPU (unsigned)v going down */
942 #define CPU_DOWN_FAILED 0x0006 /* CPU (unsigned)v NOT going down */
943 #define CPU_DEAD 0x0007 /* CPU (unsigned)v dead */
944 #define CPU_DYING 0x0008 /* CPU (unsigned)v not running any task,
945 * not handling interrupts, soon dead */
946 #define CPU_POST_DEAD 0x0009 /* CPU (unsigned)v dead, cpu_hotplug
947 * lock is dropped */
948
949 /* Used for CPU hotplug events occuring while tasks are frozen due to a suspend
950 * operation in progress
951 */
952 #define CPU_TASKS_FROZEN 0x0010
953
954 #define CPU_ONLINE_FROZEN (CPU_ONLINE | CPU_TASKS_FROZEN)
955 #define CPU_UP_PREPARE_FROZEN (CPU_UP_PREPARE | CPU_TASKS_FROZEN)
956 #define CPU_UP_CANCELED_FROZEN (CPU_UP_CANCELED | CPU_TASKS_FROZEN)
957 #define CPU_DOWN_PREPARE_FROZEN (CPU_DOWN_PREPARE | CPU_TASKS_FROZEN)
958 #define CPU_DOWN_FAILED_FROZEN (CPU_DOWN_FAILED | CPU_TASKS_FROZEN)
959 #define CPU_DEAD_FROZEN (CPU_DEAD | CPU_TASKS_FROZEN)
960 #define CPU_DYING_FROZEN (CPU_DYING | CPU_TASKS_FROZEN)
961
962 /* Hibernation and suspend events */
963 #define PM_HIBERNATION_PREPARE 0x0001 /* Going to hibernate */
964 #define PM_POST_HIBERNATION 0x0002 /* Hibernation finished */
965 #define PM_SUSPEND_PREPARE 0x0003 /* Going to suspend the system */
966 #define PM_POST_SUSPEND 0x0004 /* Suspend finished */
967 #define PM_RESTORE_PREPARE 0x0005 /* Going to restore a saved image */
968 #define PM_POST_RESTORE 0x0006 /* Restore failed */
969
970 #define NOTIFY_DONE 0x0000 /* Don't care */
971 #define NOTIFY_OK 0x0001 /* Suits me */
972 #define NOTIFY_STOP_MASK 0x8000 /* Don't call further */
973 #define NOTIFY_BAD (NOTIFY_STOP_MASK|0x0002)
974 /* Bad/Veto action */
975 /*
976 * Clean way to return from the notifier and stop further calls.
977 */
978 #define NOTIFY_STOP (NOTIFY_OK|NOTIFY_STOP_MASK)
979
980 /*
981 * Bug checks.
982 */
983
984 #define BUG_ON(c) do { if (!(c)) abort(); } while (0)
985
986 /*
987 * Initialization -- Must be called before calling any primitives.
988 */
989
990 static void smp_init(void)
991 {
992 int i;
993
994 spin_lock_init(&__thread_id_map_mutex);
995 __thread_id_map[0] = pthread_self();
996 for (i = 1; i < NR_THREADS; i++)
997 __thread_id_map[i] = __THREAD_ID_MAP_EMPTY;
998 init_per_thread(smp_processor_id, 0);
999 if (pthread_key_create(&thread_id_key, NULL) != 0) {
1000 perror("pthread_key_create");
1001 exit(-1);
1002 }
1003 }
1004
1005 /* Taken from the Linux kernel source tree, so GPLv2-only!!! */
1006
1007 #ifndef _LINUX_LIST_H
1008 #define _LINUX_LIST_H
1009
1010 #define LIST_POISON1 ((void *) 0x00100100)
1011 #define LIST_POISON2 ((void *) 0x00200200)
1012
1013 #define container_of(ptr, type, member) ({ \
1014 const typeof( ((type *)0)->member ) *__mptr = (ptr); \
1015 (type *)( (char *)__mptr - offsetof(type,member) );})
1016
1017 #if 0
1018
1019 /*
1020 * Simple doubly linked list implementation.
1021 *
1022 * Some of the internal functions ("__xxx") are useful when
1023 * manipulating whole lists rather than single entries, as
1024 * sometimes we already know the next/prev entries and we can
1025 * generate better code by using them directly rather than
1026 * using the generic single-entry routines.
1027 */
1028
1029 struct list_head {
1030 struct list_head *next, *prev;
1031 };
1032
1033 #define LIST_HEAD_INIT(name) { &(name), &(name) }
1034
1035 #define LIST_HEAD(name) \
1036 struct list_head name = LIST_HEAD_INIT(name)
1037
1038 static inline void INIT_LIST_HEAD(struct list_head *list)
1039 {
1040 list->next = list;
1041 list->prev = list;
1042 }
1043
1044 /*
1045 * Insert a new entry between two known consecutive entries.
1046 *
1047 * This is only for internal list manipulation where we know
1048 * the prev/next entries already!
1049 */
1050 #ifndef CONFIG_DEBUG_LIST
1051 static inline void __list_add(struct list_head *new,
1052 struct list_head *prev,
1053 struct list_head *next)
1054 {
1055 next->prev = new;
1056 new->next = next;
1057 new->prev = prev;
1058 prev->next = new;
1059 }
1060 #else
1061 extern void __list_add(struct list_head *new,
1062 struct list_head *prev,
1063 struct list_head *next);
1064 #endif
1065
1066 /**
1067 * list_add - add a new entry
1068 * @new: new entry to be added
1069 * @head: list head to add it after
1070 *
1071 * Insert a new entry after the specified head.
1072 * This is good for implementing stacks.
1073 */
1074 static inline void list_add(struct list_head *new, struct list_head *head)
1075 {
1076 __list_add(new, head, head->next);
1077 }
1078
1079
1080 /**
1081 * list_add_tail - add a new entry
1082 * @new: new entry to be added
1083 * @head: list head to add it before
1084 *
1085 * Insert a new entry before the specified head.
1086 * This is useful for implementing queues.
1087 */
1088 static inline void list_add_tail(struct list_head *new, struct list_head *head)
1089 {
1090 __list_add(new, head->prev, head);
1091 }
1092
1093 /*
1094 * Delete a list entry by making the prev/next entries
1095 * point to each other.
1096 *
1097 * This is only for internal list manipulation where we know
1098 * the prev/next entries already!
1099 */
1100 static inline void __list_del(struct list_head * prev, struct list_head * next)
1101 {
1102 next->prev = prev;
1103 prev->next = next;
1104 }
1105
1106 /**
1107 * list_del - deletes entry from list.
1108 * @entry: the element to delete from the list.
1109 * Note: list_empty() on entry does not return true after this, the entry is
1110 * in an undefined state.
1111 */
1112 #ifndef CONFIG_DEBUG_LIST
1113 static inline void list_del(struct list_head *entry)
1114 {
1115 __list_del(entry->prev, entry->next);
1116 entry->next = LIST_POISON1;
1117 entry->prev = LIST_POISON2;
1118 }
1119 #else
1120 extern void list_del(struct list_head *entry);
1121 #endif
1122
1123 /**
1124 * list_replace - replace old entry by new one
1125 * @old : the element to be replaced
1126 * @new : the new element to insert
1127 *
1128 * If @old was empty, it will be overwritten.
1129 */
1130 static inline void list_replace(struct list_head *old,
1131 struct list_head *new)
1132 {
1133 new->next = old->next;
1134 new->next->prev = new;
1135 new->prev = old->prev;
1136 new->prev->next = new;
1137 }
1138
1139 static inline void list_replace_init(struct list_head *old,
1140 struct list_head *new)
1141 {
1142 list_replace(old, new);
1143 INIT_LIST_HEAD(old);
1144 }
1145
1146 /**
1147 * list_del_init - deletes entry from list and reinitialize it.
1148 * @entry: the element to delete from the list.
1149 */
1150 static inline void list_del_init(struct list_head *entry)
1151 {
1152 __list_del(entry->prev, entry->next);
1153 INIT_LIST_HEAD(entry);
1154 }
1155
1156 /**
1157 * list_move - delete from one list and add as another's head
1158 * @list: the entry to move
1159 * @head: the head that will precede our entry
1160 */
1161 static inline void list_move(struct list_head *list, struct list_head *head)
1162 {
1163 __list_del(list->prev, list->next);
1164 list_add(list, head);
1165 }
1166
1167 /**
1168 * list_move_tail - delete from one list and add as another's tail
1169 * @list: the entry to move
1170 * @head: the head that will follow our entry
1171 */
1172 static inline void list_move_tail(struct list_head *list,
1173 struct list_head *head)
1174 {
1175 __list_del(list->prev, list->next);
1176 list_add_tail(list, head);
1177 }
1178
1179 /**
1180 * list_is_last - tests whether @list is the last entry in list @head
1181 * @list: the entry to test
1182 * @head: the head of the list
1183 */
1184 static inline int list_is_last(const struct list_head *list,
1185 const struct list_head *head)
1186 {
1187 return list->next == head;
1188 }
1189
1190 /**
1191 * list_empty - tests whether a list is empty
1192 * @head: the list to test.
1193 */
1194 static inline int list_empty(const struct list_head *head)
1195 {
1196 return head->next == head;
1197 }
1198
1199 /**
1200 * list_empty_careful - tests whether a list is empty and not being modified
1201 * @head: the list to test
1202 *
1203 * Description:
1204 * tests whether a list is empty _and_ checks that no other CPU might be
1205 * in the process of modifying either member (next or prev)
1206 *
1207 * NOTE: using list_empty_careful() without synchronization
1208 * can only be safe if the only activity that can happen
1209 * to the list entry is list_del_init(). Eg. it cannot be used
1210 * if another CPU could re-list_add() it.
1211 */
1212 static inline int list_empty_careful(const struct list_head *head)
1213 {
1214 struct list_head *next = head->next;
1215 return (next == head) && (next == head->prev);
1216 }
1217
1218 /**
1219 * list_is_singular - tests whether a list has just one entry.
1220 * @head: the list to test.
1221 */
1222 static inline int list_is_singular(const struct list_head *head)
1223 {
1224 return !list_empty(head) && (head->next == head->prev);
1225 }
1226
1227 static inline void __list_cut_position(struct list_head *list,
1228 struct list_head *head, struct list_head *entry)
1229 {
1230 struct list_head *new_first = entry->next;
1231 list->next = head->next;
1232 list->next->prev = list;
1233 list->prev = entry;
1234 entry->next = list;
1235 head->next = new_first;
1236 new_first->prev = head;
1237 }
1238
1239 /**
1240 * list_cut_position - cut a list into two
1241 * @list: a new list to add all removed entries
1242 * @head: a list with entries
1243 * @entry: an entry within head, could be the head itself
1244 * and if so we won't cut the list
1245 *
1246 * This helper moves the initial part of @head, up to and
1247 * including @entry, from @head to @list. You should
1248 * pass on @entry an element you know is on @head. @list
1249 * should be an empty list or a list you do not care about
1250 * losing its data.
1251 *
1252 */
1253 static inline void list_cut_position(struct list_head *list,
1254 struct list_head *head, struct list_head *entry)
1255 {
1256 if (list_empty(head))
1257 return;
1258 if (list_is_singular(head) &&
1259 (head->next != entry && head != entry))
1260 return;
1261 if (entry == head)
1262 INIT_LIST_HEAD(list);
1263 else
1264 __list_cut_position(list, head, entry);
1265 }
1266
1267 static inline void __list_splice(const struct list_head *list,
1268 struct list_head *prev,
1269 struct list_head *next)
1270 {
1271 struct list_head *first = list->next;
1272 struct list_head *last = list->prev;
1273
1274 first->prev = prev;
1275 prev->next = first;
1276
1277 last->next = next;
1278 next->prev = last;
1279 }
1280
1281 /**
1282 * list_splice - join two lists, this is designed for stacks
1283 * @list: the new list to add.
1284 * @head: the place to add it in the first list.
1285 */
1286 static inline void list_splice(const struct list_head *list,
1287 struct list_head *head)
1288 {
1289 if (!list_empty(list))
1290 __list_splice(list, head, head->next);
1291 }
1292
1293 /**
1294 * list_splice_tail - join two lists, each list being a queue
1295 * @list: the new list to add.
1296 * @head: the place to add it in the first list.
1297 */
1298 static inline void list_splice_tail(struct list_head *list,
1299 struct list_head *head)
1300 {
1301 if (!list_empty(list))
1302 __list_splice(list, head->prev, head);
1303 }
1304
1305 /**
1306 * list_splice_init - join two lists and reinitialise the emptied list.
1307 * @list: the new list to add.
1308 * @head: the place to add it in the first list.
1309 *
1310 * The list at @list is reinitialised
1311 */
1312 static inline void list_splice_init(struct list_head *list,
1313 struct list_head *head)
1314 {
1315 if (!list_empty(list)) {
1316 __list_splice(list, head, head->next);
1317 INIT_LIST_HEAD(list);
1318 }
1319 }
1320
1321 /**
1322 * list_splice_tail_init - join two lists and reinitialise the emptied list
1323 * @list: the new list to add.
1324 * @head: the place to add it in the first list.
1325 *
1326 * Each of the lists is a queue.
1327 * The list at @list is reinitialised
1328 */
1329 static inline void list_splice_tail_init(struct list_head *list,
1330 struct list_head *head)
1331 {
1332 if (!list_empty(list)) {
1333 __list_splice(list, head->prev, head);
1334 INIT_LIST_HEAD(list);
1335 }
1336 }
1337
1338 /**
1339 * list_entry - get the struct for this entry
1340 * @ptr: the &struct list_head pointer.
1341 * @type: the type of the struct this is embedded in.
1342 * @member: the name of the list_struct within the struct.
1343 */
1344 #define list_entry(ptr, type, member) \
1345 container_of(ptr, type, member)
1346
1347 /**
1348 * list_first_entry - get the first element from a list
1349 * @ptr: the list head to take the element from.
1350 * @type: the type of the struct this is embedded in.
1351 * @member: the name of the list_struct within the struct.
1352 *
1353 * Note, that list is expected to be not empty.
1354 */
1355 #define list_first_entry(ptr, type, member) \
1356 list_entry((ptr)->next, type, member)
1357
1358 /**
1359 * list_for_each - iterate over a list
1360 * @pos: the &struct list_head to use as a loop cursor.
1361 * @head: the head for your list.
1362 */
1363 #define list_for_each(pos, head) \
1364 for (pos = (head)->next; prefetch(pos->next), pos != (head); \
1365 pos = pos->next)
1366
1367 /**
1368 * __list_for_each - iterate over a list
1369 * @pos: the &struct list_head to use as a loop cursor.
1370 * @head: the head for your list.
1371 *
1372 * This variant differs from list_for_each() in that it's the
1373 * simplest possible list iteration code, no prefetching is done.
1374 * Use this for code that knows the list to be very short (empty
1375 * or 1 entry) most of the time.
1376 */
1377 #define __list_for_each(pos, head) \
1378 for (pos = (head)->next; pos != (head); pos = pos->next)
1379
1380 /**
1381 * list_for_each_prev - iterate over a list backwards
1382 * @pos: the &struct list_head to use as a loop cursor.
1383 * @head: the head for your list.
1384 */
1385 #define list_for_each_prev(pos, head) \
1386 for (pos = (head)->prev; prefetch(pos->prev), pos != (head); \
1387 pos = pos->prev)
1388
1389 /**
1390 * list_for_each_safe - iterate over a list safe against removal of list entry
1391 * @pos: the &struct list_head to use as a loop cursor.
1392 * @n: another &struct list_head to use as temporary storage
1393 * @head: the head for your list.
1394 */
1395 #define list_for_each_safe(pos, n, head) \
1396 for (pos = (head)->next, n = pos->next; pos != (head); \
1397 pos = n, n = pos->next)
1398
1399 /**
1400 * list_for_each_prev_safe - iterate over a list backwards safe against removal of list entry
1401 * @pos: the &struct list_head to use as a loop cursor.
1402 * @n: another &struct list_head to use as temporary storage
1403 * @head: the head for your list.
1404 */
1405 #define list_for_each_prev_safe(pos, n, head) \
1406 for (pos = (head)->prev, n = pos->prev; \
1407 prefetch(pos->prev), pos != (head); \
1408 pos = n, n = pos->prev)
1409
1410 /**
1411 * list_for_each_entry - iterate over list of given type
1412 * @pos: the type * to use as a loop cursor.
1413 * @head: the head for your list.
1414 * @member: the name of the list_struct within the struct.
1415 */
1416 #define list_for_each_entry(pos, head, member) \
1417 for (pos = list_entry((head)->next, typeof(*pos), member); \
1418 prefetch(pos->member.next), &pos->member != (head); \
1419 pos = list_entry(pos->member.next, typeof(*pos), member))
1420
1421 /**
1422 * list_for_each_entry_reverse - iterate backwards over list of given type.
1423 * @pos: the type * to use as a loop cursor.
1424 * @head: the head for your list.
1425 * @member: the name of the list_struct within the struct.
1426 */
1427 #define list_for_each_entry_reverse(pos, head, member) \
1428 for (pos = list_entry((head)->prev, typeof(*pos), member); \
1429 prefetch(pos->member.prev), &pos->member != (head); \
1430 pos = list_entry(pos->member.prev, typeof(*pos), member))
1431
1432 /**
1433 * list_prepare_entry - prepare a pos entry for use in list_for_each_entry_continue()
1434 * @pos: the type * to use as a start point
1435 * @head: the head of the list
1436 * @member: the name of the list_struct within the struct.
1437 *
1438 * Prepares a pos entry for use as a start point in list_for_each_entry_continue().
1439 */
1440 #define list_prepare_entry(pos, head, member) \
1441 ((pos) ? : list_entry(head, typeof(*pos), member))
1442
1443 /**
1444 * list_for_each_entry_continue - continue iteration over list of given type
1445 * @pos: the type * to use as a loop cursor.
1446 * @head: the head for your list.
1447 * @member: the name of the list_struct within the struct.
1448 *
1449 * Continue to iterate over list of given type, continuing after
1450 * the current position.
1451 */
1452 #define list_for_each_entry_continue(pos, head, member) \
1453 for (pos = list_entry(pos->member.next, typeof(*pos), member); \
1454 prefetch(pos->member.next), &pos->member != (head); \
1455 pos = list_entry(pos->member.next, typeof(*pos), member))
1456
1457 /**
1458 * list_for_each_entry_continue_reverse - iterate backwards from the given point
1459 * @pos: the type * to use as a loop cursor.
1460 * @head: the head for your list.
1461 * @member: the name of the list_struct within the struct.
1462 *
1463 * Start to iterate over list of given type backwards, continuing after
1464 * the current position.
1465 */
1466 #define list_for_each_entry_continue_reverse(pos, head, member) \
1467 for (pos = list_entry(pos->member.prev, typeof(*pos), member); \
1468 prefetch(pos->member.prev), &pos->member != (head); \
1469 pos = list_entry(pos->member.prev, typeof(*pos), member))
1470
1471 /**
1472 * list_for_each_entry_from - iterate over list of given type from the current point
1473 * @pos: the type * to use as a loop cursor.
1474 * @head: the head for your list.
1475 * @member: the name of the list_struct within the struct.
1476 *
1477 * Iterate over list of given type, continuing from current position.
1478 */
1479 #define list_for_each_entry_from(pos, head, member) \
1480 for (; prefetch(pos->member.next), &pos->member != (head); \
1481 pos = list_entry(pos->member.next, typeof(*pos), member))
1482
1483 /**
1484 * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry
1485 * @pos: the type * to use as a loop cursor.
1486 * @n: another type * to use as temporary storage
1487 * @head: the head for your list.
1488 * @member: the name of the list_struct within the struct.
1489 */
1490 #define list_for_each_entry_safe(pos, n, head, member) \
1491 for (pos = list_entry((head)->next, typeof(*pos), member), \
1492 n = list_entry(pos->member.next, typeof(*pos), member); \
1493 &pos->member != (head); \
1494 pos = n, n = list_entry(n->member.next, typeof(*n), member))
1495
1496 /**
1497 * list_for_each_entry_safe_continue
1498 * @pos: the type * to use as a loop cursor.
1499 * @n: another type * to use as temporary storage
1500 * @head: the head for your list.
1501 * @member: the name of the list_struct within the struct.
1502 *
1503 * Iterate over list of given type, continuing after current point,
1504 * safe against removal of list entry.
1505 */
1506 #define list_for_each_entry_safe_continue(pos, n, head, member) \
1507 for (pos = list_entry(pos->member.next, typeof(*pos), member), \
1508 n = list_entry(pos->member.next, typeof(*pos), member); \
1509 &pos->member != (head); \
1510 pos = n, n = list_entry(n->member.next, typeof(*n), member))
1511
1512 /**
1513 * list_for_each_entry_safe_from
1514 * @pos: the type * to use as a loop cursor.
1515 * @n: another type * to use as temporary storage
1516 * @head: the head for your list.
1517 * @member: the name of the list_struct within the struct.
1518 *
1519 * Iterate over list of given type from current point, safe against
1520 * removal of list entry.
1521 */
1522 #define list_for_each_entry_safe_from(pos, n, head, member) \
1523 for (n = list_entry(pos->member.next, typeof(*pos), member); \
1524 &pos->member != (head); \
1525 pos = n, n = list_entry(n->member.next, typeof(*n), member))
1526
1527 /**
1528 * list_for_each_entry_safe_reverse
1529 * @pos: the type * to use as a loop cursor.
1530 * @n: another type * to use as temporary storage
1531 * @head: the head for your list.
1532 * @member: the name of the list_struct within the struct.
1533 *
1534 * Iterate backwards over list of given type, safe against removal
1535 * of list entry.
1536 */
1537 #define list_for_each_entry_safe_reverse(pos, n, head, member) \
1538 for (pos = list_entry((head)->prev, typeof(*pos), member), \
1539 n = list_entry(pos->member.prev, typeof(*pos), member); \
1540 &pos->member != (head); \
1541 pos = n, n = list_entry(n->member.prev, typeof(*n), member))
1542
1543 #endif //0
1544
1545 /*
1546 * Double linked lists with a single pointer list head.
1547 * Mostly useful for hash tables where the two pointer list head is
1548 * too wasteful.
1549 * You lose the ability to access the tail in O(1).
1550 */
1551
1552 struct hlist_head {
1553 struct hlist_node *first;
1554 };
1555
1556 struct hlist_node {
1557 struct hlist_node *next, **pprev;
1558 };
1559
1560 #define HLIST_HEAD_INIT { .first = NULL }
1561 #define HLIST_HEAD(name) struct hlist_head name = { .first = NULL }
1562 #define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL)
1563 static inline void INIT_HLIST_NODE(struct hlist_node *h)
1564 {
1565 h->next = NULL;
1566 h->pprev = NULL;
1567 }
1568
1569 static inline int hlist_unhashed(const struct hlist_node *h)
1570 {
1571 return !h->pprev;
1572 }
1573
1574 static inline int hlist_empty(const struct hlist_head *h)
1575 {
1576 return !h->first;
1577 }
1578
1579 static inline void __hlist_del(struct hlist_node *n)
1580 {
1581 struct hlist_node *next = n->next;
1582 struct hlist_node **pprev = n->pprev;
1583 *pprev = next;
1584 if (next)
1585 next->pprev = pprev;
1586 }
1587
1588 static inline void hlist_del(struct hlist_node *n)
1589 {
1590 __hlist_del(n);
1591 n->next = LIST_POISON1;
1592 n->pprev = LIST_POISON2;
1593 }
1594
1595 static inline void hlist_del_init(struct hlist_node *n)
1596 {
1597 if (!hlist_unhashed(n)) {
1598 __hlist_del(n);
1599 INIT_HLIST_NODE(n);
1600 }
1601 }
1602
1603 static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
1604 {
1605 struct hlist_node *first = h->first;
1606 n->next = first;
1607 if (first)
1608 first->pprev = &n->next;
1609 h->first = n;
1610 n->pprev = &h->first;
1611 }
1612
1613 /* next must be != NULL */
1614 static inline void hlist_add_before(struct hlist_node *n,
1615 struct hlist_node *next)
1616 {
1617 n->pprev = next->pprev;
1618 n->next = next;
1619 next->pprev = &n->next;
1620 *(n->pprev) = n;
1621 }
1622
1623 static inline void hlist_add_after(struct hlist_node *n,
1624 struct hlist_node *next)
1625 {
1626 next->next = n->next;
1627 n->next = next;
1628 next->pprev = &n->next;
1629
1630 if(next->next)
1631 next->next->pprev = &next->next;
1632 }
1633
1634 /*
1635 * Move a list from one list head to another. Fixup the pprev
1636 * reference of the first entry if it exists.
1637 */
1638 static inline void hlist_move_list(struct hlist_head *old,
1639 struct hlist_head *new)
1640 {
1641 new->first = old->first;
1642 if (new->first)
1643 new->first->pprev = &new->first;
1644 old->first = NULL;
1645 }
1646
1647 #define hlist_entry(ptr, type, member) container_of(ptr,type,member)
1648
1649 #define hlist_for_each(pos, head) \
1650 for (pos = (head)->first; pos && ({ prefetch(pos->next); 1; }); \
1651 pos = pos->next)
1652
1653 #define hlist_for_each_safe(pos, n, head) \
1654 for (pos = (head)->first; pos && ({ n = pos->next; 1; }); \
1655 pos = n)
1656
1657 /**
1658 * hlist_for_each_entry - iterate over list of given type
1659 * @tpos: the type * to use as a loop cursor.
1660 * @pos: the &struct hlist_node to use as a loop cursor.
1661 * @head: the head for your list.
1662 * @member: the name of the hlist_node within the struct.
1663 */
1664 #define hlist_for_each_entry(tpos, pos, head, member) \
1665 for (pos = (head)->first; \
1666 pos && ({ prefetch(pos->next); 1;}) && \
1667 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
1668 pos = pos->next)
1669
1670 /**
1671 * hlist_for_each_entry_continue - iterate over a hlist continuing after current point
1672 * @tpos: the type * to use as a loop cursor.
1673 * @pos: the &struct hlist_node to use as a loop cursor.
1674 * @member: the name of the hlist_node within the struct.
1675 */
1676 #define hlist_for_each_entry_continue(tpos, pos, member) \
1677 for (pos = (pos)->next; \
1678 pos && ({ prefetch(pos->next); 1;}) && \
1679 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
1680 pos = pos->next)
1681
1682 /**
1683 * hlist_for_each_entry_from - iterate over a hlist continuing from current point
1684 * @tpos: the type * to use as a loop cursor.
1685 * @pos: the &struct hlist_node to use as a loop cursor.
1686 * @member: the name of the hlist_node within the struct.
1687 */
1688 #define hlist_for_each_entry_from(tpos, pos, member) \
1689 for (; pos && ({ prefetch(pos->next); 1;}) && \
1690 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
1691 pos = pos->next)
1692
1693 /**
1694 * hlist_for_each_entry_safe - iterate over list of given type safe against removal of list entry
1695 * @tpos: the type * to use as a loop cursor.
1696 * @pos: the &struct hlist_node to use as a loop cursor.
1697 * @n: another &struct hlist_node to use as temporary storage
1698 * @head: the head for your list.
1699 * @member: the name of the hlist_node within the struct.
1700 */
1701 #define hlist_for_each_entry_safe(tpos, pos, n, head, member) \
1702 for (pos = (head)->first; \
1703 pos && ({ n = pos->next; 1; }) && \
1704 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
1705 pos = n)
1706
1707 #endif
1708
1709 #endif
This page took 0.073254 seconds and 4 git commands to generate.