uatomic compat: complete i386 support
[urcu.git] / tests / api_x86.h
CommitLineData
6d0ce021
PM
1/* MECHANICALLY GENERATED, DO NOT EDIT!!! */
2
1a43bbd8 3#ifndef _INCLUDE_API_H
6d0ce021
PM
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
22b63ec4
MD
29#include <urcu/arch.h>
30
6d0ce021
PM
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-i386.h: Expose x86 atomic instructions. 80486 and better only.
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 only due to inclusion
56 * of Linux-kernel code.
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
b4e52e3e 77/* #define CACHE_LINE_SIZE 64 */
6d0ce021
PM
78#define ____cacheline_internodealigned_in_smp \
79 __attribute__((__aligned__(1 << 6)))
80
81#define LOCK_PREFIX "lock ; "
82
6ee91d83
MD
83#if 0 /* duplicate with arch_atomic.h */
84
6d0ce021
PM
85/*
86 * Atomic data structure, initialization, and access.
87 */
88
89typedef 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/**
101 * atomic_add - add integer to atomic variable
102 * @i: integer value to add
103 * @v: pointer of type atomic_t
104 *
105 * Atomically adds @i to @v.
106 */
107static __inline__ void atomic_add(int i, atomic_t *v)
108{
109 __asm__ __volatile__(
110 LOCK_PREFIX "addl %1,%0"
111 :"+m" (v->counter)
112 :"ir" (i));
113}
114
115/**
116 * atomic_sub - subtract the atomic variable
117 * @i: integer value to subtract
118 * @v: pointer of type atomic_t
119 *
120 * Atomically subtracts @i from @v.
121 */
122static __inline__ void atomic_sub(int i, atomic_t *v)
123{
124 __asm__ __volatile__(
125 LOCK_PREFIX "subl %1,%0"
126 :"+m" (v->counter)
127 :"ir" (i));
128}
129
130/**
131 * atomic_sub_and_test - subtract value from variable and test result
132 * @i: integer value to subtract
133 * @v: pointer of type atomic_t
134 *
135 * Atomically subtracts @i from @v and returns
136 * true if the result is zero, or false for all
137 * other cases.
138 */
139static __inline__ int atomic_sub_and_test(int i, atomic_t *v)
140{
141 unsigned char c;
142
143 __asm__ __volatile__(
144 LOCK_PREFIX "subl %2,%0; sete %1"
145 :"+m" (v->counter), "=qm" (c)
146 :"ir" (i) : "memory");
147 return c;
148}
149
150/**
151 * atomic_inc - increment atomic variable
152 * @v: pointer of type atomic_t
153 *
154 * Atomically increments @v by 1.
155 */
156static __inline__ void atomic_inc(atomic_t *v)
157{
158 __asm__ __volatile__(
159 LOCK_PREFIX "incl %0"
160 :"+m" (v->counter));
161}
162
163/**
164 * atomic_dec - decrement atomic variable
165 * @v: pointer of type atomic_t
166 *
167 * Atomically decrements @v by 1.
168 */
169static __inline__ void atomic_dec(atomic_t *v)
170{
171 __asm__ __volatile__(
172 LOCK_PREFIX "decl %0"
173 :"+m" (v->counter));
174}
175
176/**
177 * atomic_dec_and_test - decrement and test
178 * @v: pointer of type atomic_t
179 *
180 * Atomically decrements @v by 1 and
181 * returns true if the result is 0, or false for all other
182 * cases.
183 */
184static __inline__ int atomic_dec_and_test(atomic_t *v)
185{
186 unsigned char c;
187
188 __asm__ __volatile__(
189 LOCK_PREFIX "decl %0; sete %1"
190 :"+m" (v->counter), "=qm" (c)
191 : : "memory");
192 return c != 0;
193}
194
195/**
196 * atomic_inc_and_test - increment and test
197 * @v: pointer of type atomic_t
198 *
199 * Atomically increments @v by 1
200 * and returns true if the result is zero, or false for all
201 * other cases.
202 */
203static __inline__ int atomic_inc_and_test(atomic_t *v)
204{
205 unsigned char c;
206
207 __asm__ __volatile__(
208 LOCK_PREFIX "incl %0; sete %1"
209 :"+m" (v->counter), "=qm" (c)
210 : : "memory");
211 return c != 0;
212}
213
214/**
215 * atomic_add_negative - add and test if negative
216 * @v: pointer of type atomic_t
217 * @i: integer value to add
218 *
219 * Atomically adds @i to @v and returns true
220 * if the result is negative, or false when
221 * result is greater than or equal to zero.
222 */
223static __inline__ int atomic_add_negative(int i, atomic_t *v)
224{
225 unsigned char c;
226
227 __asm__ __volatile__(
228 LOCK_PREFIX "addl %2,%0; sets %1"
229 :"+m" (v->counter), "=qm" (c)
230 :"ir" (i) : "memory");
231 return c;
232}
233
234/**
235 * atomic_add_return - add and return
236 * @v: pointer of type atomic_t
237 * @i: integer value to add
238 *
239 * Atomically adds @i to @v and returns @i + @v
240 */
241static __inline__ int atomic_add_return(int i, atomic_t *v)
242{
243 int __i;
244
245 __i = i;
246 __asm__ __volatile__(
247 LOCK_PREFIX "xaddl %0, %1;"
248 :"=r"(i)
249 :"m"(v->counter), "0"(i));
250 return i + __i;
251}
252
253static __inline__ int atomic_sub_return(int i, atomic_t *v)
254{
255 return atomic_add_return(-i,v);
256}
257
258static inline unsigned int
259cmpxchg(volatile long *ptr, long oldval, long newval)
260{
261 unsigned long retval;
262
263 asm("# cmpxchg\n"
264 "lock; cmpxchgl %4,(%2)\n"
265 "# end atomic_cmpxchg4"
266 : "=a" (retval), "=m" (*ptr)
267 : "r" (ptr), "0" (oldval), "r" (newval), "m" (*ptr)
268 : "cc");
269 return (retval);
270}
271
272#define atomic_cmpxchg(v, old, new) ((int)cmpxchg(&((v)->counter), old, new))
273#define atomic_xchg(v, new) (xchg(&((v)->counter), new))
274
275/**
276 * atomic_add_unless - add unless the number is a given value
277 * @v: pointer of type atomic_t
278 * @a: the amount to add to v...
279 * @u: ...unless v is equal to u.
280 *
281 * Atomically adds @a to @v, so long as it was not @u.
282 * Returns non-zero if @v was not @u, and zero otherwise.
283 */
284#define atomic_add_unless(v, a, u) \
285({ \
286 int c, old; \
287 c = atomic_read(v); \
288 for (;;) { \
289 if (unlikely(c == (u))) \
290 break; \
291 old = atomic_cmpxchg((v), c, c + (a)); \
292 if (likely(old == c)) \
293 break; \
294 c = old; \
295 } \
296 c != (u); \
297})
298#define atomic_inc_not_zero(v) atomic_add_unless((v), 1, 0)
299
300#define atomic_inc_return(v) (atomic_add_return(1,v))
301#define atomic_dec_return(v) (atomic_sub_return(1,v))
302
303/* These are x86-specific, used by some header files */
304#define atomic_clear_mask(mask, addr) \
305__asm__ __volatile__(LOCK_PREFIX "andl %0,%1" \
306: : "r" (~(mask)),"m" (*addr) : "memory")
307
308#define atomic_set_mask(mask, addr) \
309__asm__ __volatile__(LOCK_PREFIX "orl %0,%1" \
310: : "r" (mask),"m" (*(addr)) : "memory")
311
312/* Atomic operations are already serializing on x86 */
313#define smp_mb__before_atomic_dec() barrier()
314#define smp_mb__after_atomic_dec() barrier()
315#define smp_mb__before_atomic_inc() barrier()
316#define smp_mb__after_atomic_inc() barrier()
317
6ee91d83
MD
318#endif //0
319
6d0ce021
PM
320/*
321 * api_pthreads.h: API mapping to pthreads environment.
322 *
323 * This program is free software; you can redistribute it and/or modify
324 * it under the terms of the GNU General Public License as published by
325 * the Free Software Foundation; either version 2 of the License, or
326 * (at your option) any later version. However, please note that much
327 * of the code in this file derives from the Linux kernel, and that such
328 * code may not be available except under GPLv2.
329 *
330 * This program is distributed in the hope that it will be useful,
331 * but WITHOUT ANY WARRANTY; without even the implied warranty of
332 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
333 * GNU General Public License for more details.
334 *
335 * You should have received a copy of the GNU General Public License
336 * along with this program; if not, write to the Free Software
337 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
338 *
339 * Copyright (c) 2006 Paul E. McKenney, IBM.
340 */
341
342#include <stdio.h>
343#include <stdlib.h>
344#include <errno.h>
345#include <limits.h>
346#include <sys/types.h>
347#define __USE_GNU
348#include <pthread.h>
349#include <sched.h>
350#include <sys/param.h>
351/* #include "atomic.h" */
352
353/*
354 * Compiler magic.
355 */
6d0ce021
PM
356#define container_of(ptr, type, member) ({ \
357 const typeof( ((type *)0)->member ) *__mptr = (ptr); \
358 (type *)( (char *)__mptr - offsetof(type,member) );})
6d0ce021
PM
359
360/*
361 * Default machine parameters.
362 */
363
364#ifndef CACHE_LINE_SIZE
22b63ec4 365/* #define CACHE_LINE_SIZE 128 */
6d0ce021
PM
366#endif /* #ifndef CACHE_LINE_SIZE */
367
368/*
369 * Exclusive locking primitives.
370 */
371
372typedef pthread_mutex_t spinlock_t;
373
374#define DEFINE_SPINLOCK(lock) spinlock_t lock = PTHREAD_MUTEX_INITIALIZER;
375#define __SPIN_LOCK_UNLOCKED(lockp) PTHREAD_MUTEX_INITIALIZER
376
377static void spin_lock_init(spinlock_t *sp)
378{
379 if (pthread_mutex_init(sp, NULL) != 0) {
380 perror("spin_lock_init:pthread_mutex_init");
381 exit(-1);
382 }
383}
384
385static void spin_lock(spinlock_t *sp)
386{
387 if (pthread_mutex_lock(sp) != 0) {
388 perror("spin_lock:pthread_mutex_lock");
389 exit(-1);
390 }
391}
392
6d0ce021
PM
393static void spin_unlock(spinlock_t *sp)
394{
395 if (pthread_mutex_unlock(sp) != 0) {
396 perror("spin_unlock:pthread_mutex_unlock");
397 exit(-1);
398 }
399}
400
401#define spin_lock_irqsave(l, f) do { f = 1; spin_lock(l); } while (0)
402#define spin_unlock_irqrestore(l, f) do { f = 0; spin_unlock(l); } while (0)
403
6d0ce021
PM
404/*
405 * Thread creation/destruction primitives.
406 */
407
408typedef pthread_t thread_id_t;
409
410#define NR_THREADS 128
411
412#define __THREAD_ID_MAP_EMPTY 0
413#define __THREAD_ID_MAP_WAITING 1
414thread_id_t __thread_id_map[NR_THREADS];
415spinlock_t __thread_id_map_mutex;
416
417#define for_each_thread(t) \
418 for (t = 0; t < NR_THREADS; t++)
419
420#define for_each_running_thread(t) \
421 for (t = 0; t < NR_THREADS; t++) \
422 if ((__thread_id_map[t] != __THREAD_ID_MAP_EMPTY) && \
423 (__thread_id_map[t] != __THREAD_ID_MAP_WAITING))
424
425pthread_key_t thread_id_key;
426
427static int __smp_thread_id(void)
428{
429 int i;
430 thread_id_t tid = pthread_self();
431
432 for (i = 0; i < NR_THREADS; i++) {
433 if (__thread_id_map[i] == tid) {
434 long v = i + 1; /* must be non-NULL. */
435
436 if (pthread_setspecific(thread_id_key, (void *)v) != 0) {
437 perror("pthread_setspecific");
438 exit(-1);
439 }
440 return i;
441 }
442 }
443 spin_lock(&__thread_id_map_mutex);
444 for (i = 0; i < NR_THREADS; i++) {
445 if (__thread_id_map[i] == tid)
446 spin_unlock(&__thread_id_map_mutex);
447 return i;
448 }
449 spin_unlock(&__thread_id_map_mutex);
0578089f
PM
450 fprintf(stderr, "smp_thread_id: Rogue thread, id: %d(%#x)\n",
451 (int)tid, (int)tid);
6d0ce021
PM
452 exit(-1);
453}
454
455static int smp_thread_id(void)
456{
457 void *id;
458
459 id = pthread_getspecific(thread_id_key);
460 if (id == NULL)
461 return __smp_thread_id();
462 return (long)(id - 1);
463}
464
465static thread_id_t create_thread(void *(*func)(void *), void *arg)
466{
467 thread_id_t tid;
468 int i;
469
470 spin_lock(&__thread_id_map_mutex);
471 for (i = 0; i < NR_THREADS; i++) {
472 if (__thread_id_map[i] == __THREAD_ID_MAP_EMPTY)
473 break;
474 }
475 if (i >= NR_THREADS) {
476 spin_unlock(&__thread_id_map_mutex);
477 fprintf(stderr, "Thread limit of %d exceeded!\n", NR_THREADS);
478 exit(-1);
479 }
480 __thread_id_map[i] = __THREAD_ID_MAP_WAITING;
481 spin_unlock(&__thread_id_map_mutex);
482 if (pthread_create(&tid, NULL, func, arg) != 0) {
483 perror("create_thread:pthread_create");
484 exit(-1);
485 }
486 __thread_id_map[i] = tid;
487 return tid;
488}
489
490static void *wait_thread(thread_id_t tid)
491{
492 int i;
493 void *vp;
494
495 for (i = 0; i < NR_THREADS; i++) {
496 if (__thread_id_map[i] == tid)
497 break;
498 }
499 if (i >= NR_THREADS){
0578089f
PM
500 fprintf(stderr, "wait_thread: bad tid = %d(%#x)\n",
501 (int)tid, (int)tid);
6d0ce021
PM
502 exit(-1);
503 }
504 if (pthread_join(tid, &vp) != 0) {
505 perror("wait_thread:pthread_join");
506 exit(-1);
507 }
508 __thread_id_map[i] = __THREAD_ID_MAP_EMPTY;
509 return vp;
510}
511
512static void wait_all_threads(void)
513{
514 int i;
515 thread_id_t tid;
516
517 for (i = 1; i < NR_THREADS; i++) {
518 tid = __thread_id_map[i];
519 if (tid != __THREAD_ID_MAP_EMPTY &&
520 tid != __THREAD_ID_MAP_WAITING)
521 (void)wait_thread(tid);
522 }
523}
524
525static void run_on(int cpu)
526{
527 cpu_set_t mask;
528
529 CPU_ZERO(&mask);
530 CPU_SET(cpu, &mask);
531 sched_setaffinity(0, sizeof(mask), &mask);
532}
533
534/*
535 * timekeeping -- very crude -- should use MONOTONIC...
536 */
537
538long long get_microseconds(void)
539{
540 struct timeval tv;
541
542 if (gettimeofday(&tv, NULL) != 0)
543 abort();
544 return ((long long)tv.tv_sec) * 1000000LL + (long long)tv.tv_usec;
545}
546
547/*
548 * Per-thread variables.
549 */
550
551#define DEFINE_PER_THREAD(type, name) \
552 struct { \
553 __typeof__(type) v \
554 __attribute__((__aligned__(CACHE_LINE_SIZE))); \
555 } __per_thread_##name[NR_THREADS];
556#define DECLARE_PER_THREAD(type, name) extern DEFINE_PER_THREAD(type, name)
557
558#define per_thread(name, thread) __per_thread_##name[thread].v
559#define __get_thread_var(name) per_thread(name, smp_thread_id())
560
561#define init_per_thread(name, v) \
562 do { \
563 int __i_p_t_i; \
564 for (__i_p_t_i = 0; __i_p_t_i < NR_THREADS; __i_p_t_i++) \
565 per_thread(name, __i_p_t_i) = v; \
566 } while (0)
567
568/*
569 * CPU traversal primitives.
570 */
571
572#ifndef NR_CPUS
573#define NR_CPUS 16
574#endif /* #ifndef NR_CPUS */
575
576#define for_each_possible_cpu(cpu) \
577 for (cpu = 0; cpu < NR_CPUS; cpu++)
578#define for_each_online_cpu(cpu) \
579 for (cpu = 0; cpu < NR_CPUS; cpu++)
580
581/*
582 * Per-CPU variables.
583 */
584
585#define DEFINE_PER_CPU(type, name) \
586 struct { \
587 __typeof__(type) v \
588 __attribute__((__aligned__(CACHE_LINE_SIZE))); \
589 } __per_cpu_##name[NR_CPUS]
590#define DECLARE_PER_CPU(type, name) extern DEFINE_PER_CPU(type, name)
591
592DEFINE_PER_THREAD(int, smp_processor_id);
593
6d0ce021
PM
594#define per_cpu(name, thread) __per_cpu_##name[thread].v
595#define __get_cpu_var(name) per_cpu(name, smp_processor_id())
596
597#define init_per_cpu(name, v) \
598 do { \
599 int __i_p_c_i; \
600 for (__i_p_c_i = 0; __i_p_c_i < NR_CPUS; __i_p_c_i++) \
601 per_cpu(name, __i_p_c_i) = v; \
602 } while (0)
603
604/*
605 * CPU state checking (crowbarred).
606 */
607
608#define idle_cpu(cpu) 0
609#define in_softirq() 1
610#define hardirq_count() 0
611#define PREEMPT_SHIFT 0
612#define SOFTIRQ_SHIFT (PREEMPT_SHIFT + PREEMPT_BITS)
613#define HARDIRQ_SHIFT (SOFTIRQ_SHIFT + SOFTIRQ_BITS)
614#define PREEMPT_BITS 8
615#define SOFTIRQ_BITS 8
616
617/*
618 * CPU hotplug.
619 */
620
621struct notifier_block {
622 int (*notifier_call)(struct notifier_block *, unsigned long, void *);
623 struct notifier_block *next;
624 int priority;
625};
626
627#define CPU_ONLINE 0x0002 /* CPU (unsigned)v is up */
628#define CPU_UP_PREPARE 0x0003 /* CPU (unsigned)v coming up */
629#define CPU_UP_CANCELED 0x0004 /* CPU (unsigned)v NOT coming up */
630#define CPU_DOWN_PREPARE 0x0005 /* CPU (unsigned)v going down */
631#define CPU_DOWN_FAILED 0x0006 /* CPU (unsigned)v NOT going down */
632#define CPU_DEAD 0x0007 /* CPU (unsigned)v dead */
633#define CPU_DYING 0x0008 /* CPU (unsigned)v not running any task,
634 * not handling interrupts, soon dead */
635#define CPU_POST_DEAD 0x0009 /* CPU (unsigned)v dead, cpu_hotplug
636 * lock is dropped */
637
638/* Used for CPU hotplug events occuring while tasks are frozen due to a suspend
639 * operation in progress
640 */
641#define CPU_TASKS_FROZEN 0x0010
642
643#define CPU_ONLINE_FROZEN (CPU_ONLINE | CPU_TASKS_FROZEN)
644#define CPU_UP_PREPARE_FROZEN (CPU_UP_PREPARE | CPU_TASKS_FROZEN)
645#define CPU_UP_CANCELED_FROZEN (CPU_UP_CANCELED | CPU_TASKS_FROZEN)
646#define CPU_DOWN_PREPARE_FROZEN (CPU_DOWN_PREPARE | CPU_TASKS_FROZEN)
647#define CPU_DOWN_FAILED_FROZEN (CPU_DOWN_FAILED | CPU_TASKS_FROZEN)
648#define CPU_DEAD_FROZEN (CPU_DEAD | CPU_TASKS_FROZEN)
649#define CPU_DYING_FROZEN (CPU_DYING | CPU_TASKS_FROZEN)
650
651/* Hibernation and suspend events */
652#define PM_HIBERNATION_PREPARE 0x0001 /* Going to hibernate */
653#define PM_POST_HIBERNATION 0x0002 /* Hibernation finished */
654#define PM_SUSPEND_PREPARE 0x0003 /* Going to suspend the system */
655#define PM_POST_SUSPEND 0x0004 /* Suspend finished */
656#define PM_RESTORE_PREPARE 0x0005 /* Going to restore a saved image */
657#define PM_POST_RESTORE 0x0006 /* Restore failed */
658
659#define NOTIFY_DONE 0x0000 /* Don't care */
660#define NOTIFY_OK 0x0001 /* Suits me */
661#define NOTIFY_STOP_MASK 0x8000 /* Don't call further */
662#define NOTIFY_BAD (NOTIFY_STOP_MASK|0x0002)
663 /* Bad/Veto action */
664/*
665 * Clean way to return from the notifier and stop further calls.
666 */
667#define NOTIFY_STOP (NOTIFY_OK|NOTIFY_STOP_MASK)
668
669/*
670 * Bug checks.
671 */
672
673#define BUG_ON(c) do { if (!(c)) abort(); } while (0)
674
675/*
676 * Initialization -- Must be called before calling any primitives.
677 */
678
679static void smp_init(void)
680{
681 int i;
682
683 spin_lock_init(&__thread_id_map_mutex);
684 __thread_id_map[0] = pthread_self();
685 for (i = 1; i < NR_THREADS; i++)
686 __thread_id_map[i] = __THREAD_ID_MAP_EMPTY;
687 init_per_thread(smp_processor_id, 0);
688 if (pthread_key_create(&thread_id_key, NULL) != 0) {
689 perror("pthread_key_create");
690 exit(-1);
691 }
692}
693
694/* Taken from the Linux kernel source tree, so GPLv2-only!!! */
695
696#ifndef _LINUX_LIST_H
697#define _LINUX_LIST_H
698
699#define LIST_POISON1 ((void *) 0x00100100)
700#define LIST_POISON2 ((void *) 0x00200200)
701
6d0ce021
PM
702#define container_of(ptr, type, member) ({ \
703 const typeof( ((type *)0)->member ) *__mptr = (ptr); \
704 (type *)( (char *)__mptr - offsetof(type,member) );})
705
63ff4873
MD
706#if 0
707
6d0ce021
PM
708/*
709 * Simple doubly linked list implementation.
710 *
711 * Some of the internal functions ("__xxx") are useful when
712 * manipulating whole lists rather than single entries, as
713 * sometimes we already know the next/prev entries and we can
714 * generate better code by using them directly rather than
715 * using the generic single-entry routines.
716 */
717
718struct list_head {
719 struct list_head *next, *prev;
720};
721
722#define LIST_HEAD_INIT(name) { &(name), &(name) }
723
724#define LIST_HEAD(name) \
725 struct list_head name = LIST_HEAD_INIT(name)
726
727static inline void INIT_LIST_HEAD(struct list_head *list)
728{
729 list->next = list;
730 list->prev = list;
731}
732
733/*
734 * Insert a new entry between two known consecutive entries.
735 *
736 * This is only for internal list manipulation where we know
737 * the prev/next entries already!
738 */
739#ifndef CONFIG_DEBUG_LIST
740static inline void __list_add(struct list_head *new,
741 struct list_head *prev,
742 struct list_head *next)
743{
744 next->prev = new;
745 new->next = next;
746 new->prev = prev;
747 prev->next = new;
748}
749#else
750extern void __list_add(struct list_head *new,
751 struct list_head *prev,
752 struct list_head *next);
753#endif
754
755/**
756 * list_add - add a new entry
757 * @new: new entry to be added
758 * @head: list head to add it after
759 *
760 * Insert a new entry after the specified head.
761 * This is good for implementing stacks.
762 */
763static inline void list_add(struct list_head *new, struct list_head *head)
764{
765 __list_add(new, head, head->next);
766}
767
768
769/**
770 * list_add_tail - add a new entry
771 * @new: new entry to be added
772 * @head: list head to add it before
773 *
774 * Insert a new entry before the specified head.
775 * This is useful for implementing queues.
776 */
777static inline void list_add_tail(struct list_head *new, struct list_head *head)
778{
779 __list_add(new, head->prev, head);
780}
781
782/*
783 * Delete a list entry by making the prev/next entries
784 * point to each other.
785 *
786 * This is only for internal list manipulation where we know
787 * the prev/next entries already!
788 */
789static inline void __list_del(struct list_head * prev, struct list_head * next)
790{
791 next->prev = prev;
792 prev->next = next;
793}
794
795/**
796 * list_del - deletes entry from list.
797 * @entry: the element to delete from the list.
798 * Note: list_empty() on entry does not return true after this, the entry is
799 * in an undefined state.
800 */
801#ifndef CONFIG_DEBUG_LIST
802static inline void list_del(struct list_head *entry)
803{
804 __list_del(entry->prev, entry->next);
805 entry->next = LIST_POISON1;
806 entry->prev = LIST_POISON2;
807}
808#else
809extern void list_del(struct list_head *entry);
810#endif
811
812/**
813 * list_replace - replace old entry by new one
814 * @old : the element to be replaced
815 * @new : the new element to insert
816 *
817 * If @old was empty, it will be overwritten.
818 */
819static inline void list_replace(struct list_head *old,
820 struct list_head *new)
821{
822 new->next = old->next;
823 new->next->prev = new;
824 new->prev = old->prev;
825 new->prev->next = new;
826}
827
828static inline void list_replace_init(struct list_head *old,
829 struct list_head *new)
830{
831 list_replace(old, new);
832 INIT_LIST_HEAD(old);
833}
834
835/**
836 * list_del_init - deletes entry from list and reinitialize it.
837 * @entry: the element to delete from the list.
838 */
839static inline void list_del_init(struct list_head *entry)
840{
841 __list_del(entry->prev, entry->next);
842 INIT_LIST_HEAD(entry);
843}
844
845/**
846 * list_move - delete from one list and add as another's head
847 * @list: the entry to move
848 * @head: the head that will precede our entry
849 */
850static inline void list_move(struct list_head *list, struct list_head *head)
851{
852 __list_del(list->prev, list->next);
853 list_add(list, head);
854}
855
856/**
857 * list_move_tail - delete from one list and add as another's tail
858 * @list: the entry to move
859 * @head: the head that will follow our entry
860 */
861static inline void list_move_tail(struct list_head *list,
862 struct list_head *head)
863{
864 __list_del(list->prev, list->next);
865 list_add_tail(list, head);
866}
867
868/**
869 * list_is_last - tests whether @list is the last entry in list @head
870 * @list: the entry to test
871 * @head: the head of the list
872 */
873static inline int list_is_last(const struct list_head *list,
874 const struct list_head *head)
875{
876 return list->next == head;
877}
878
879/**
880 * list_empty - tests whether a list is empty
881 * @head: the list to test.
882 */
883static inline int list_empty(const struct list_head *head)
884{
885 return head->next == head;
886}
887
888/**
889 * list_empty_careful - tests whether a list is empty and not being modified
890 * @head: the list to test
891 *
892 * Description:
893 * tests whether a list is empty _and_ checks that no other CPU might be
894 * in the process of modifying either member (next or prev)
895 *
896 * NOTE: using list_empty_careful() without synchronization
897 * can only be safe if the only activity that can happen
898 * to the list entry is list_del_init(). Eg. it cannot be used
899 * if another CPU could re-list_add() it.
900 */
901static inline int list_empty_careful(const struct list_head *head)
902{
903 struct list_head *next = head->next;
904 return (next == head) && (next == head->prev);
905}
906
907/**
908 * list_is_singular - tests whether a list has just one entry.
909 * @head: the list to test.
910 */
911static inline int list_is_singular(const struct list_head *head)
912{
913 return !list_empty(head) && (head->next == head->prev);
914}
915
916static inline void __list_cut_position(struct list_head *list,
917 struct list_head *head, struct list_head *entry)
918{
919 struct list_head *new_first = entry->next;
920 list->next = head->next;
921 list->next->prev = list;
922 list->prev = entry;
923 entry->next = list;
924 head->next = new_first;
925 new_first->prev = head;
926}
927
928/**
929 * list_cut_position - cut a list into two
930 * @list: a new list to add all removed entries
931 * @head: a list with entries
932 * @entry: an entry within head, could be the head itself
933 * and if so we won't cut the list
934 *
935 * This helper moves the initial part of @head, up to and
936 * including @entry, from @head to @list. You should
937 * pass on @entry an element you know is on @head. @list
938 * should be an empty list or a list you do not care about
939 * losing its data.
940 *
941 */
942static inline void list_cut_position(struct list_head *list,
943 struct list_head *head, struct list_head *entry)
944{
945 if (list_empty(head))
946 return;
947 if (list_is_singular(head) &&
948 (head->next != entry && head != entry))
949 return;
950 if (entry == head)
951 INIT_LIST_HEAD(list);
952 else
953 __list_cut_position(list, head, entry);
954}
955
956static inline void __list_splice(const struct list_head *list,
957 struct list_head *prev,
958 struct list_head *next)
959{
960 struct list_head *first = list->next;
961 struct list_head *last = list->prev;
962
963 first->prev = prev;
964 prev->next = first;
965
966 last->next = next;
967 next->prev = last;
968}
969
970/**
971 * list_splice - join two lists, this is designed for stacks
972 * @list: the new list to add.
973 * @head: the place to add it in the first list.
974 */
975static inline void list_splice(const struct list_head *list,
976 struct list_head *head)
977{
978 if (!list_empty(list))
979 __list_splice(list, head, head->next);
980}
981
982/**
983 * list_splice_tail - join two lists, each list being a queue
984 * @list: the new list to add.
985 * @head: the place to add it in the first list.
986 */
987static inline void list_splice_tail(struct list_head *list,
988 struct list_head *head)
989{
990 if (!list_empty(list))
991 __list_splice(list, head->prev, head);
992}
993
994/**
995 * list_splice_init - join two lists and reinitialise the emptied list.
996 * @list: the new list to add.
997 * @head: the place to add it in the first list.
998 *
999 * The list at @list is reinitialised
1000 */
1001static inline void list_splice_init(struct list_head *list,
1002 struct list_head *head)
1003{
1004 if (!list_empty(list)) {
1005 __list_splice(list, head, head->next);
1006 INIT_LIST_HEAD(list);
1007 }
1008}
1009
1010/**
1011 * list_splice_tail_init - join two lists and reinitialise the emptied list
1012 * @list: the new list to add.
1013 * @head: the place to add it in the first list.
1014 *
1015 * Each of the lists is a queue.
1016 * The list at @list is reinitialised
1017 */
1018static inline void list_splice_tail_init(struct list_head *list,
1019 struct list_head *head)
1020{
1021 if (!list_empty(list)) {
1022 __list_splice(list, head->prev, head);
1023 INIT_LIST_HEAD(list);
1024 }
1025}
1026
1027/**
1028 * list_entry - get the struct for this entry
1029 * @ptr: the &struct list_head pointer.
1030 * @type: the type of the struct this is embedded in.
1031 * @member: the name of the list_struct within the struct.
1032 */
1033#define list_entry(ptr, type, member) \
1034 container_of(ptr, type, member)
1035
1036/**
1037 * list_first_entry - get the first element from a list
1038 * @ptr: the list head to take the element from.
1039 * @type: the type of the struct this is embedded in.
1040 * @member: the name of the list_struct within the struct.
1041 *
1042 * Note, that list is expected to be not empty.
1043 */
1044#define list_first_entry(ptr, type, member) \
1045 list_entry((ptr)->next, type, member)
1046
1047/**
1048 * list_for_each - iterate over a list
1049 * @pos: the &struct list_head to use as a loop cursor.
1050 * @head: the head for your list.
1051 */
1052#define list_for_each(pos, head) \
1053 for (pos = (head)->next; prefetch(pos->next), pos != (head); \
1054 pos = pos->next)
1055
1056/**
1057 * __list_for_each - iterate over a list
1058 * @pos: the &struct list_head to use as a loop cursor.
1059 * @head: the head for your list.
1060 *
1061 * This variant differs from list_for_each() in that it's the
1062 * simplest possible list iteration code, no prefetching is done.
1063 * Use this for code that knows the list to be very short (empty
1064 * or 1 entry) most of the time.
1065 */
1066#define __list_for_each(pos, head) \
1067 for (pos = (head)->next; pos != (head); pos = pos->next)
1068
1069/**
1070 * list_for_each_prev - iterate over a list backwards
1071 * @pos: the &struct list_head to use as a loop cursor.
1072 * @head: the head for your list.
1073 */
1074#define list_for_each_prev(pos, head) \
1075 for (pos = (head)->prev; prefetch(pos->prev), pos != (head); \
1076 pos = pos->prev)
1077
1078/**
1079 * list_for_each_safe - iterate over a list safe against removal of list entry
1080 * @pos: the &struct list_head to use as a loop cursor.
1081 * @n: another &struct list_head to use as temporary storage
1082 * @head: the head for your list.
1083 */
1084#define list_for_each_safe(pos, n, head) \
1085 for (pos = (head)->next, n = pos->next; pos != (head); \
1086 pos = n, n = pos->next)
1087
1088/**
1089 * list_for_each_prev_safe - iterate over a list backwards safe against removal of list entry
1090 * @pos: the &struct list_head to use as a loop cursor.
1091 * @n: another &struct list_head to use as temporary storage
1092 * @head: the head for your list.
1093 */
1094#define list_for_each_prev_safe(pos, n, head) \
1095 for (pos = (head)->prev, n = pos->prev; \
1096 prefetch(pos->prev), pos != (head); \
1097 pos = n, n = pos->prev)
1098
1099/**
1100 * list_for_each_entry - iterate over list of given type
1101 * @pos: the type * to use as a loop cursor.
1102 * @head: the head for your list.
1103 * @member: the name of the list_struct within the struct.
1104 */
1105#define list_for_each_entry(pos, head, member) \
1106 for (pos = list_entry((head)->next, typeof(*pos), member); \
1107 prefetch(pos->member.next), &pos->member != (head); \
1108 pos = list_entry(pos->member.next, typeof(*pos), member))
1109
1110/**
1111 * list_for_each_entry_reverse - iterate backwards over list of given type.
1112 * @pos: the type * to use as a loop cursor.
1113 * @head: the head for your list.
1114 * @member: the name of the list_struct within the struct.
1115 */
1116#define list_for_each_entry_reverse(pos, head, member) \
1117 for (pos = list_entry((head)->prev, typeof(*pos), member); \
1118 prefetch(pos->member.prev), &pos->member != (head); \
1119 pos = list_entry(pos->member.prev, typeof(*pos), member))
1120
1121/**
1122 * list_prepare_entry - prepare a pos entry for use in list_for_each_entry_continue()
1123 * @pos: the type * to use as a start point
1124 * @head: the head of the list
1125 * @member: the name of the list_struct within the struct.
1126 *
1127 * Prepares a pos entry for use as a start point in list_for_each_entry_continue().
1128 */
1129#define list_prepare_entry(pos, head, member) \
1130 ((pos) ? : list_entry(head, typeof(*pos), member))
1131
1132/**
1133 * list_for_each_entry_continue - continue iteration over list of given type
1134 * @pos: the type * to use as a loop cursor.
1135 * @head: the head for your list.
1136 * @member: the name of the list_struct within the struct.
1137 *
1138 * Continue to iterate over list of given type, continuing after
1139 * the current position.
1140 */
1141#define list_for_each_entry_continue(pos, head, member) \
1142 for (pos = list_entry(pos->member.next, typeof(*pos), member); \
1143 prefetch(pos->member.next), &pos->member != (head); \
1144 pos = list_entry(pos->member.next, typeof(*pos), member))
1145
1146/**
1147 * list_for_each_entry_continue_reverse - iterate backwards from the given point
1148 * @pos: the type * to use as a loop cursor.
1149 * @head: the head for your list.
1150 * @member: the name of the list_struct within the struct.
1151 *
1152 * Start to iterate over list of given type backwards, continuing after
1153 * the current position.
1154 */
1155#define list_for_each_entry_continue_reverse(pos, head, member) \
1156 for (pos = list_entry(pos->member.prev, typeof(*pos), member); \
1157 prefetch(pos->member.prev), &pos->member != (head); \
1158 pos = list_entry(pos->member.prev, typeof(*pos), member))
1159
1160/**
1161 * list_for_each_entry_from - iterate over list of given type from the current point
1162 * @pos: the type * to use as a loop cursor.
1163 * @head: the head for your list.
1164 * @member: the name of the list_struct within the struct.
1165 *
1166 * Iterate over list of given type, continuing from current position.
1167 */
1168#define list_for_each_entry_from(pos, head, member) \
1169 for (; prefetch(pos->member.next), &pos->member != (head); \
1170 pos = list_entry(pos->member.next, typeof(*pos), member))
1171
1172/**
1173 * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry
1174 * @pos: the type * to use as a loop cursor.
1175 * @n: another type * to use as temporary storage
1176 * @head: the head for your list.
1177 * @member: the name of the list_struct within the struct.
1178 */
1179#define list_for_each_entry_safe(pos, n, head, member) \
1180 for (pos = list_entry((head)->next, typeof(*pos), member), \
1181 n = list_entry(pos->member.next, typeof(*pos), member); \
1182 &pos->member != (head); \
1183 pos = n, n = list_entry(n->member.next, typeof(*n), member))
1184
1185/**
1186 * list_for_each_entry_safe_continue
1187 * @pos: the type * to use as a loop cursor.
1188 * @n: another type * to use as temporary storage
1189 * @head: the head for your list.
1190 * @member: the name of the list_struct within the struct.
1191 *
1192 * Iterate over list of given type, continuing after current point,
1193 * safe against removal of list entry.
1194 */
1195#define list_for_each_entry_safe_continue(pos, n, head, member) \
1196 for (pos = list_entry(pos->member.next, typeof(*pos), member), \
1197 n = list_entry(pos->member.next, typeof(*pos), member); \
1198 &pos->member != (head); \
1199 pos = n, n = list_entry(n->member.next, typeof(*n), member))
1200
1201/**
1202 * list_for_each_entry_safe_from
1203 * @pos: the type * to use as a loop cursor.
1204 * @n: another type * to use as temporary storage
1205 * @head: the head for your list.
1206 * @member: the name of the list_struct within the struct.
1207 *
1208 * Iterate over list of given type from current point, safe against
1209 * removal of list entry.
1210 */
1211#define list_for_each_entry_safe_from(pos, n, head, member) \
1212 for (n = list_entry(pos->member.next, typeof(*pos), member); \
1213 &pos->member != (head); \
1214 pos = n, n = list_entry(n->member.next, typeof(*n), member))
1215
1216/**
1217 * list_for_each_entry_safe_reverse
1218 * @pos: the type * to use as a loop cursor.
1219 * @n: another type * to use as temporary storage
1220 * @head: the head for your list.
1221 * @member: the name of the list_struct within the struct.
1222 *
1223 * Iterate backwards over list of given type, safe against removal
1224 * of list entry.
1225 */
1226#define list_for_each_entry_safe_reverse(pos, n, head, member) \
1227 for (pos = list_entry((head)->prev, typeof(*pos), member), \
1228 n = list_entry(pos->member.prev, typeof(*pos), member); \
1229 &pos->member != (head); \
1230 pos = n, n = list_entry(n->member.prev, typeof(*n), member))
1231
63ff4873
MD
1232#endif //0
1233
6d0ce021
PM
1234/*
1235 * Double linked lists with a single pointer list head.
1236 * Mostly useful for hash tables where the two pointer list head is
1237 * too wasteful.
1238 * You lose the ability to access the tail in O(1).
1239 */
1240
1241struct hlist_head {
1242 struct hlist_node *first;
1243};
1244
1245struct hlist_node {
1246 struct hlist_node *next, **pprev;
1247};
1248
1249#define HLIST_HEAD_INIT { .first = NULL }
1250#define HLIST_HEAD(name) struct hlist_head name = { .first = NULL }
1251#define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL)
1252static inline void INIT_HLIST_NODE(struct hlist_node *h)
1253{
1254 h->next = NULL;
1255 h->pprev = NULL;
1256}
1257
1258static inline int hlist_unhashed(const struct hlist_node *h)
1259{
1260 return !h->pprev;
1261}
1262
1263static inline int hlist_empty(const struct hlist_head *h)
1264{
1265 return !h->first;
1266}
1267
1268static inline void __hlist_del(struct hlist_node *n)
1269{
1270 struct hlist_node *next = n->next;
1271 struct hlist_node **pprev = n->pprev;
1272 *pprev = next;
1273 if (next)
1274 next->pprev = pprev;
1275}
1276
1277static inline void hlist_del(struct hlist_node *n)
1278{
1279 __hlist_del(n);
1280 n->next = LIST_POISON1;
1281 n->pprev = LIST_POISON2;
1282}
1283
1284static inline void hlist_del_init(struct hlist_node *n)
1285{
1286 if (!hlist_unhashed(n)) {
1287 __hlist_del(n);
1288 INIT_HLIST_NODE(n);
1289 }
1290}
1291
1292static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
1293{
1294 struct hlist_node *first = h->first;
1295 n->next = first;
1296 if (first)
1297 first->pprev = &n->next;
1298 h->first = n;
1299 n->pprev = &h->first;
1300}
1301
1302/* next must be != NULL */
1303static inline void hlist_add_before(struct hlist_node *n,
1304 struct hlist_node *next)
1305{
1306 n->pprev = next->pprev;
1307 n->next = next;
1308 next->pprev = &n->next;
1309 *(n->pprev) = n;
1310}
1311
1312static inline void hlist_add_after(struct hlist_node *n,
1313 struct hlist_node *next)
1314{
1315 next->next = n->next;
1316 n->next = next;
1317 next->pprev = &n->next;
1318
1319 if(next->next)
1320 next->next->pprev = &next->next;
1321}
1322
1323/*
1324 * Move a list from one list head to another. Fixup the pprev
1325 * reference of the first entry if it exists.
1326 */
1327static inline void hlist_move_list(struct hlist_head *old,
1328 struct hlist_head *new)
1329{
1330 new->first = old->first;
1331 if (new->first)
1332 new->first->pprev = &new->first;
1333 old->first = NULL;
1334}
1335
1336#define hlist_entry(ptr, type, member) container_of(ptr,type,member)
1337
1338#define hlist_for_each(pos, head) \
1339 for (pos = (head)->first; pos && ({ prefetch(pos->next); 1; }); \
1340 pos = pos->next)
1341
1342#define hlist_for_each_safe(pos, n, head) \
1343 for (pos = (head)->first; pos && ({ n = pos->next; 1; }); \
1344 pos = n)
1345
1346/**
1347 * hlist_for_each_entry - iterate over list of given type
1348 * @tpos: the type * to use as a loop cursor.
1349 * @pos: the &struct hlist_node to use as a loop cursor.
1350 * @head: the head for your list.
1351 * @member: the name of the hlist_node within the struct.
1352 */
1353#define hlist_for_each_entry(tpos, pos, head, member) \
1354 for (pos = (head)->first; \
1355 pos && ({ prefetch(pos->next); 1;}) && \
1356 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
1357 pos = pos->next)
1358
1359/**
1360 * hlist_for_each_entry_continue - iterate over a hlist continuing after current point
1361 * @tpos: the type * to use as a loop cursor.
1362 * @pos: the &struct hlist_node to use as a loop cursor.
1363 * @member: the name of the hlist_node within the struct.
1364 */
1365#define hlist_for_each_entry_continue(tpos, pos, member) \
1366 for (pos = (pos)->next; \
1367 pos && ({ prefetch(pos->next); 1;}) && \
1368 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
1369 pos = pos->next)
1370
1371/**
1372 * hlist_for_each_entry_from - iterate over a hlist continuing from current point
1373 * @tpos: the type * to use as a loop cursor.
1374 * @pos: the &struct hlist_node to use as a loop cursor.
1375 * @member: the name of the hlist_node within the struct.
1376 */
1377#define hlist_for_each_entry_from(tpos, pos, member) \
1378 for (; pos && ({ prefetch(pos->next); 1;}) && \
1379 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
1380 pos = pos->next)
1381
1382/**
1383 * hlist_for_each_entry_safe - iterate over list of given type safe against removal of list entry
1384 * @tpos: the type * to use as a loop cursor.
1385 * @pos: the &struct hlist_node to use as a loop cursor.
1386 * @n: another &struct hlist_node to use as temporary storage
1387 * @head: the head for your list.
1388 * @member: the name of the hlist_node within the struct.
1389 */
1390#define hlist_for_each_entry_safe(tpos, pos, n, head, member) \
1391 for (pos = (head)->first; \
1392 pos && ({ n = pos->next; 1; }) && \
1393 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
1394 pos = n)
1395
1396#endif
1a43bbd8
MD
1397
1398#endif
This page took 0.08783 seconds and 4 git commands to generate.