1 /* MECHANICALLY GENERATED, DO NOT EDIT!!! */
9 * common.h: Common Linux kernel-isms.
11 * This program is free software; you can redistribute it and/or modify
12 * it under the terms of the GNU General Public License as published by
13 * the Free Software Foundation; but version 2 of the License only due
14 * to code included from the Linux kernel.
16 * This program is distributed in the hope that it will be useful,
17 * but WITHOUT ANY WARRANTY; without even the implied warranty of
18 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
19 * GNU General Public License for more details.
21 * You should have received a copy of the GNU General Public License
22 * along with this program; if not, write to the Free Software
23 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
25 * Copyright (c) 2006 Paul E. McKenney, IBM.
27 * Much code taken from the Linux kernel. For such code, the option
28 * to redistribute under later versions of GPL might not be available.
31 #include <urcu/arch.h>
33 #ifndef __always_inline
34 #define __always_inline inline
37 #define BUILD_BUG_ON(condition) ((void)sizeof(char[1 - 2*!!(condition)]))
38 #define BUILD_BUG_ON_ZERO(e) (sizeof(char[1 - 2 * !!(e)]) - 1)
41 # define stringify_in_c(...) __VA_ARGS__
42 # define ASM_CONST(x) x
44 /* This version of stringify will deal with commas... */
45 # define __stringify_in_c(...) #__VA_ARGS__
46 # define stringify_in_c(...) __stringify_in_c(__VA_ARGS__) " "
47 # define __ASM_CONST(x) x##UL
48 # define ASM_CONST(x) __ASM_CONST(x)
53 * arch-i386.h: Expose x86 atomic instructions. 80486 and better only.
55 * This program is free software; you can redistribute it and/or modify
56 * it under the terms of the GNU General Public License as published by
57 * the Free Software Foundation, but version 2 only due to inclusion
58 * of Linux-kernel code.
60 * This program is distributed in the hope that it will be useful,
61 * but WITHOUT ANY WARRANTY; without even the implied warranty of
62 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
63 * GNU General Public License for more details.
65 * You should have received a copy of the GNU General Public License
66 * along with this program; if not, write to the Free Software
67 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
69 * Copyright (c) 2006 Paul E. McKenney, IBM.
71 * Much code taken from the Linux kernel. For such code, the option
72 * to redistribute under later versions of GPL might not be available.
79 /* #define CAA_CACHE_LINE_SIZE 64 */
80 #define ____cacheline_internodealigned_in_smp \
81 __attribute__((__aligned__(1 << 6)))
83 #define LOCK_PREFIX "lock ; "
85 #if 0 /* duplicate with arch_atomic.h */
88 * Atomic data structure, initialization, and access.
91 typedef struct { volatile int counter
; } atomic_t
;
93 #define ATOMIC_INIT(i) { (i) }
95 #define atomic_read(v) ((v)->counter)
96 #define atomic_set(v, i) (((v)->counter) = (i))
103 * atomic_add - add integer to atomic variable
104 * @i: integer value to add
105 * @v: pointer of type atomic_t
107 * Atomically adds @i to @v.
109 static __inline__
void atomic_add(int i
, atomic_t
*v
)
111 __asm__
__volatile__(
112 LOCK_PREFIX
"addl %1,%0"
118 * atomic_sub - subtract the atomic variable
119 * @i: integer value to subtract
120 * @v: pointer of type atomic_t
122 * Atomically subtracts @i from @v.
124 static __inline__
void atomic_sub(int i
, atomic_t
*v
)
126 __asm__
__volatile__(
127 LOCK_PREFIX
"subl %1,%0"
133 * atomic_sub_and_test - subtract value from variable and test result
134 * @i: integer value to subtract
135 * @v: pointer of type atomic_t
137 * Atomically subtracts @i from @v and returns
138 * true if the result is zero, or false for all
141 static __inline__
int atomic_sub_and_test(int i
, atomic_t
*v
)
145 __asm__
__volatile__(
146 LOCK_PREFIX
"subl %2,%0; sete %1"
147 :"+m" (v
->counter
), "=qm" (c
)
148 :"ir" (i
) : "memory");
153 * atomic_inc - increment atomic variable
154 * @v: pointer of type atomic_t
156 * Atomically increments @v by 1.
158 static __inline__
void atomic_inc(atomic_t
*v
)
160 __asm__
__volatile__(
161 LOCK_PREFIX
"incl %0"
166 * atomic_dec - decrement atomic variable
167 * @v: pointer of type atomic_t
169 * Atomically decrements @v by 1.
171 static __inline__
void atomic_dec(atomic_t
*v
)
173 __asm__
__volatile__(
174 LOCK_PREFIX
"decl %0"
179 * atomic_dec_and_test - decrement and test
180 * @v: pointer of type atomic_t
182 * Atomically decrements @v by 1 and
183 * returns true if the result is 0, or false for all other
186 static __inline__
int atomic_dec_and_test(atomic_t
*v
)
190 __asm__
__volatile__(
191 LOCK_PREFIX
"decl %0; sete %1"
192 :"+m" (v
->counter
), "=qm" (c
)
198 * atomic_inc_and_test - increment and test
199 * @v: pointer of type atomic_t
201 * Atomically increments @v by 1
202 * and returns true if the result is zero, or false for all
205 static __inline__
int atomic_inc_and_test(atomic_t
*v
)
209 __asm__
__volatile__(
210 LOCK_PREFIX
"incl %0; sete %1"
211 :"+m" (v
->counter
), "=qm" (c
)
217 * atomic_add_negative - add and test if negative
218 * @v: pointer of type atomic_t
219 * @i: integer value to add
221 * Atomically adds @i to @v and returns true
222 * if the result is negative, or false when
223 * result is greater than or equal to zero.
225 static __inline__
int atomic_add_negative(int i
, atomic_t
*v
)
229 __asm__
__volatile__(
230 LOCK_PREFIX
"addl %2,%0; sets %1"
231 :"+m" (v
->counter
), "=qm" (c
)
232 :"ir" (i
) : "memory");
237 * atomic_add_return - add and return
238 * @v: pointer of type atomic_t
239 * @i: integer value to add
241 * Atomically adds @i to @v and returns @i + @v
243 static __inline__
int atomic_add_return(int i
, atomic_t
*v
)
248 __asm__
__volatile__(
249 LOCK_PREFIX
"xaddl %0, %1;"
251 :"m"(v
->counter
), "0"(i
));
255 static __inline__
int atomic_sub_return(int i
, atomic_t
*v
)
257 return atomic_add_return(-i
,v
);
260 static inline unsigned int
261 cmpxchg(volatile long *ptr
, long oldval
, long newval
)
263 unsigned long retval
;
266 "lock; cmpxchgl %4,(%2)\n"
267 "# end atomic_cmpxchg4"
268 : "=a" (retval
), "=m" (*ptr
)
269 : "r" (ptr
), "0" (oldval
), "r" (newval
), "m" (*ptr
)
274 #define atomic_cmpxchg(v, old, new) ((int)cmpxchg(&((v)->counter), old, new))
275 #define atomic_xchg(v, new) (xchg(&((v)->counter), new))
278 * atomic_add_unless - add unless the number is a given value
279 * @v: pointer of type atomic_t
280 * @a: the amount to add to v...
281 * @u: ...unless v is equal to u.
283 * Atomically adds @a to @v, so long as it was not @u.
284 * Returns non-zero if @v was not @u, and zero otherwise.
286 #define atomic_add_unless(v, a, u) \
289 c = atomic_read(v); \
291 if (unlikely(c == (u))) \
293 old = atomic_cmpxchg((v), c, c + (a)); \
294 if (likely(old == c)) \
300 #define atomic_inc_not_zero(v) atomic_add_unless((v), 1, 0)
302 #define atomic_inc_return(v) (atomic_add_return(1,v))
303 #define atomic_dec_return(v) (atomic_sub_return(1,v))
305 /* These are x86-specific, used by some header files */
306 #define atomic_clear_mask(mask, addr) \
307 __asm__ __volatile__(LOCK_PREFIX "andl %0,%1" \
308 : : "r" (~(mask)),"m" (*addr) : "memory")
310 #define atomic_set_mask(mask, addr) \
311 __asm__ __volatile__(LOCK_PREFIX "orl %0,%1" \
312 : : "r" (mask),"m" (*(addr)) : "memory")
314 /* Atomic operations are already serializing on x86 */
315 #define smp_mb__before_atomic_dec() cmm_barrier()
316 #define smp_mb__after_atomic_dec() cmm_barrier()
317 #define smp_mb__before_atomic_inc() cmm_barrier()
318 #define smp_mb__after_atomic_inc() cmm_barrier()
323 * api_pthreads.h: API mapping to pthreads environment.
325 * This program is free software; you can redistribute it and/or modify
326 * it under the terms of the GNU General Public License as published by
327 * the Free Software Foundation; either version 2 of the License, or
328 * (at your option) any later version. However, please note that much
329 * of the code in this file derives from the Linux kernel, and that such
330 * code may not be available except under GPLv2.
332 * This program is distributed in the hope that it will be useful,
333 * but WITHOUT ANY WARRANTY; without even the implied warranty of
334 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
335 * GNU General Public License for more details.
337 * You should have received a copy of the GNU General Public License
338 * along with this program; if not, write to the Free Software
339 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
341 * Copyright (c) 2006 Paul E. McKenney, IBM.
348 #include <sys/types.h>
352 #include <sys/param.h>
353 /* #include "atomic.h" */
356 * Default machine parameters.
359 #ifndef CAA_CACHE_LINE_SIZE
360 /* #define CAA_CACHE_LINE_SIZE 128 */
361 #endif /* #ifndef CAA_CACHE_LINE_SIZE */
364 * Exclusive locking primitives.
367 typedef pthread_mutex_t spinlock_t
;
369 #define DEFINE_SPINLOCK(lock) spinlock_t lock = PTHREAD_MUTEX_INITIALIZER;
370 #define __SPIN_LOCK_UNLOCKED(lockp) PTHREAD_MUTEX_INITIALIZER
372 static void spin_lock_init(spinlock_t
*sp
)
374 if (pthread_mutex_init(sp
, NULL
) != 0) {
375 perror("spin_lock_init:pthread_mutex_init");
380 static void spin_lock(spinlock_t
*sp
)
382 if (pthread_mutex_lock(sp
) != 0) {
383 perror("spin_lock:pthread_mutex_lock");
388 static void spin_unlock(spinlock_t
*sp
)
390 if (pthread_mutex_unlock(sp
) != 0) {
391 perror("spin_unlock:pthread_mutex_unlock");
396 #define spin_lock_irqsave(l, f) do { f = 1; spin_lock(l); } while (0)
397 #define spin_unlock_irqrestore(l, f) do { f = 0; spin_unlock(l); } while (0)
400 * Thread creation/destruction primitives.
403 typedef pthread_t thread_id_t
;
405 #define NR_THREADS 128
407 #define __THREAD_ID_MAP_EMPTY ((thread_id_t) 0)
408 #define __THREAD_ID_MAP_WAITING ((thread_id_t) 1)
409 thread_id_t __thread_id_map
[NR_THREADS
];
410 spinlock_t __thread_id_map_mutex
;
412 #define for_each_thread(t) \
413 for (t = 0; t < NR_THREADS; t++)
415 #define for_each_running_thread(t) \
416 for (t = 0; t < NR_THREADS; t++) \
417 if ((__thread_id_map[t] != __THREAD_ID_MAP_EMPTY) && \
418 (__thread_id_map[t] != __THREAD_ID_MAP_WAITING))
420 pthread_key_t thread_id_key
;
422 static int __smp_thread_id(void)
425 thread_id_t tid
= pthread_self();
427 for (i
= 0; i
< NR_THREADS
; i
++) {
428 if (__thread_id_map
[i
] == tid
) {
429 long v
= i
+ 1; /* must be non-NULL. */
431 if (pthread_setspecific(thread_id_key
, (void *)v
) != 0) {
432 perror("pthread_setspecific");
438 spin_lock(&__thread_id_map_mutex
);
439 for (i
= 0; i
< NR_THREADS
; i
++) {
440 if (__thread_id_map
[i
] == tid
)
441 spin_unlock(&__thread_id_map_mutex
);
444 spin_unlock(&__thread_id_map_mutex
);
445 fprintf(stderr
, "smp_thread_id: Rogue thread, id: %d(%#x)\n",
450 static int smp_thread_id(void)
454 id
= pthread_getspecific(thread_id_key
);
456 return __smp_thread_id();
457 return (long)(id
- 1);
460 static thread_id_t
create_thread(void *(*func
)(void *), void *arg
)
465 spin_lock(&__thread_id_map_mutex
);
466 for (i
= 0; i
< NR_THREADS
; i
++) {
467 if (__thread_id_map
[i
] == __THREAD_ID_MAP_EMPTY
)
470 if (i
>= NR_THREADS
) {
471 spin_unlock(&__thread_id_map_mutex
);
472 fprintf(stderr
, "Thread limit of %d exceeded!\n", NR_THREADS
);
475 __thread_id_map
[i
] = __THREAD_ID_MAP_WAITING
;
476 spin_unlock(&__thread_id_map_mutex
);
477 if (pthread_create(&tid
, NULL
, func
, arg
) != 0) {
478 perror("create_thread:pthread_create");
481 __thread_id_map
[i
] = tid
;
485 static void *wait_thread(thread_id_t tid
)
490 for (i
= 0; i
< NR_THREADS
; i
++) {
491 if (__thread_id_map
[i
] == tid
)
494 if (i
>= NR_THREADS
){
495 fprintf(stderr
, "wait_thread: bad tid = %d(%#x)\n",
499 if (pthread_join(tid
, &vp
) != 0) {
500 perror("wait_thread:pthread_join");
503 __thread_id_map
[i
] = __THREAD_ID_MAP_EMPTY
;
507 static void wait_all_threads(void)
512 for (i
= 1; i
< NR_THREADS
; i
++) {
513 tid
= __thread_id_map
[i
];
514 if (tid
!= __THREAD_ID_MAP_EMPTY
&&
515 tid
!= __THREAD_ID_MAP_WAITING
)
516 (void)wait_thread(tid
);
520 #ifndef HAVE_CPU_SET_T
521 typedef unsigned long cpu_set_t
;
522 # define CPU_ZERO(cpuset) do { *(cpuset) = 0; } while(0)
523 # define CPU_SET(cpu, cpuset) do { *(cpuset) |= (1UL << (cpu)); } while(0)
526 static void run_on(int cpu
)
528 #if HAVE_SCHED_SETAFFINITY
533 #if SCHED_SETAFFINITY_ARGS == 2
534 sched_setaffinity(0, &mask
);
536 sched_setaffinity(0, sizeof(mask
), &mask
);
538 #endif /* HAVE_SCHED_SETAFFINITY */
542 * timekeeping -- very crude -- should use MONOTONIC...
545 long long get_microseconds(void)
549 if (gettimeofday(&tv
, NULL
) != 0)
551 return ((long long)tv
.tv_sec
) * 1000000LL + (long long)tv
.tv_usec
;
555 * Per-thread variables.
558 #define DEFINE_PER_THREAD(type, name) \
561 __attribute__((__aligned__(CAA_CACHE_LINE_SIZE))); \
562 } __per_thread_##name[NR_THREADS];
563 #define DECLARE_PER_THREAD(type, name) extern DEFINE_PER_THREAD(type, name)
565 #define per_thread(name, thread) __per_thread_##name[thread].v
566 #define __get_thread_var(name) per_thread(name, smp_thread_id())
568 #define init_per_thread(name, v) \
571 for (__i_p_t_i = 0; __i_p_t_i < NR_THREADS; __i_p_t_i++) \
572 per_thread(name, __i_p_t_i) = v; \
576 * CPU traversal primitives.
581 #endif /* #ifndef NR_CPUS */
583 #define for_each_possible_cpu(cpu) \
584 for (cpu = 0; cpu < NR_CPUS; cpu++)
585 #define for_each_online_cpu(cpu) \
586 for (cpu = 0; cpu < NR_CPUS; cpu++)
592 #define DEFINE_PER_CPU(type, name) \
595 __attribute__((__aligned__(CAA_CACHE_LINE_SIZE))); \
596 } __per_cpu_##name[NR_CPUS]
597 #define DECLARE_PER_CPU(type, name) extern DEFINE_PER_CPU(type, name)
599 DEFINE_PER_THREAD(int, smp_processor_id
);
601 #define per_cpu(name, thread) __per_cpu_##name[thread].v
602 #define __get_cpu_var(name) per_cpu(name, smp_processor_id())
604 #define init_per_cpu(name, v) \
607 for (__i_p_c_i = 0; __i_p_c_i < NR_CPUS; __i_p_c_i++) \
608 per_cpu(name, __i_p_c_i) = v; \
612 * CPU state checking (crowbarred).
615 #define idle_cpu(cpu) 0
616 #define in_softirq() 1
617 #define hardirq_count() 0
618 #define PREEMPT_SHIFT 0
619 #define SOFTIRQ_SHIFT (PREEMPT_SHIFT + PREEMPT_BITS)
620 #define HARDIRQ_SHIFT (SOFTIRQ_SHIFT + SOFTIRQ_BITS)
621 #define PREEMPT_BITS 8
622 #define SOFTIRQ_BITS 8
628 struct notifier_block
{
629 int (*notifier_call
)(struct notifier_block
*, unsigned long, void *);
630 struct notifier_block
*next
;
634 #define CPU_ONLINE 0x0002 /* CPU (unsigned)v is up */
635 #define CPU_UP_PREPARE 0x0003 /* CPU (unsigned)v coming up */
636 #define CPU_UP_CANCELED 0x0004 /* CPU (unsigned)v NOT coming up */
637 #define CPU_DOWN_PREPARE 0x0005 /* CPU (unsigned)v going down */
638 #define CPU_DOWN_FAILED 0x0006 /* CPU (unsigned)v NOT going down */
639 #define CPU_DEAD 0x0007 /* CPU (unsigned)v dead */
640 #define CPU_DYING 0x0008 /* CPU (unsigned)v not running any task,
641 * not handling interrupts, soon dead */
642 #define CPU_POST_DEAD 0x0009 /* CPU (unsigned)v dead, cpu_hotplug
645 /* Used for CPU hotplug events occuring while tasks are frozen due to a suspend
646 * operation in progress
648 #define CPU_TASKS_FROZEN 0x0010
650 #define CPU_ONLINE_FROZEN (CPU_ONLINE | CPU_TASKS_FROZEN)
651 #define CPU_UP_PREPARE_FROZEN (CPU_UP_PREPARE | CPU_TASKS_FROZEN)
652 #define CPU_UP_CANCELED_FROZEN (CPU_UP_CANCELED | CPU_TASKS_FROZEN)
653 #define CPU_DOWN_PREPARE_FROZEN (CPU_DOWN_PREPARE | CPU_TASKS_FROZEN)
654 #define CPU_DOWN_FAILED_FROZEN (CPU_DOWN_FAILED | CPU_TASKS_FROZEN)
655 #define CPU_DEAD_FROZEN (CPU_DEAD | CPU_TASKS_FROZEN)
656 #define CPU_DYING_FROZEN (CPU_DYING | CPU_TASKS_FROZEN)
658 /* Hibernation and suspend events */
659 #define PM_HIBERNATION_PREPARE 0x0001 /* Going to hibernate */
660 #define PM_POST_HIBERNATION 0x0002 /* Hibernation finished */
661 #define PM_SUSPEND_PREPARE 0x0003 /* Going to suspend the system */
662 #define PM_POST_SUSPEND 0x0004 /* Suspend finished */
663 #define PM_RESTORE_PREPARE 0x0005 /* Going to restore a saved image */
664 #define PM_POST_RESTORE 0x0006 /* Restore failed */
666 #define NOTIFY_DONE 0x0000 /* Don't care */
667 #define NOTIFY_OK 0x0001 /* Suits me */
668 #define NOTIFY_STOP_MASK 0x8000 /* Don't call further */
669 #define NOTIFY_BAD (NOTIFY_STOP_MASK|0x0002)
670 /* Bad/Veto action */
672 * Clean way to return from the notifier and stop further calls.
674 #define NOTIFY_STOP (NOTIFY_OK|NOTIFY_STOP_MASK)
680 #define BUG_ON(c) do { if (!(c)) abort(); } while (0)
683 * Initialization -- Must be called before calling any primitives.
686 static void smp_init(void)
690 spin_lock_init(&__thread_id_map_mutex
);
691 __thread_id_map
[0] = pthread_self();
692 for (i
= 1; i
< NR_THREADS
; i
++)
693 __thread_id_map
[i
] = __THREAD_ID_MAP_EMPTY
;
694 init_per_thread(smp_processor_id
, 0);
695 if (pthread_key_create(&thread_id_key
, NULL
) != 0) {
696 perror("pthread_key_create");
701 /* Taken from the Linux kernel source tree, so GPLv2-only!!! */
703 #ifndef _LINUX_LIST_H
704 #define _LINUX_LIST_H
706 #define LIST_POISON1 ((void *) 0x00100100)
707 #define LIST_POISON2 ((void *) 0x00200200)
712 * Simple doubly linked list implementation.
714 * Some of the internal functions ("__xxx") are useful when
715 * manipulating whole lists rather than single entries, as
716 * sometimes we already know the next/prev entries and we can
717 * generate better code by using them directly rather than
718 * using the generic single-entry routines.
721 struct cds_list_head
{
722 struct cds_list_head
*next
, *prev
;
725 #define CDS_LIST_HEAD_INIT(name) { &(name), &(name) }
727 #define CDS_LIST_HEAD(name) \
728 struct cds_list_head name = CDS_LIST_HEAD_INIT(name)
730 static inline void CDS_INIT_LIST_HEAD(struct cds_list_head
*list
)
737 * Insert a new entry between two known consecutive entries.
739 * This is only for internal list manipulation where we know
740 * the prev/next entries already!
742 #ifndef CONFIG_DEBUG_LIST
743 static inline void __cds_list_add(struct cds_list_head
*new,
744 struct cds_list_head
*prev
,
745 struct cds_list_head
*next
)
753 extern void __cds_list_add(struct cds_list_head
*new,
754 struct cds_list_head
*prev
,
755 struct cds_list_head
*next
);
759 * cds_list_add - add a new entry
760 * @new: new entry to be added
761 * @head: list head to add it after
763 * Insert a new entry after the specified head.
764 * This is good for implementing stacks.
766 static inline void cds_list_add(struct cds_list_head
*new, struct cds_list_head
*head
)
768 __cds_list_add(new, head
, head
->next
);
773 * cds_list_add_tail - add a new entry
774 * @new: new entry to be added
775 * @head: list head to add it before
777 * Insert a new entry before the specified head.
778 * This is useful for implementing queues.
780 static inline void cds_list_add_tail(struct cds_list_head
*new, struct cds_list_head
*head
)
782 __cds_list_add(new, head
->prev
, head
);
786 * Delete a list entry by making the prev/next entries
787 * point to each other.
789 * This is only for internal list manipulation where we know
790 * the prev/next entries already!
792 static inline void __cds_list_del(struct cds_list_head
* prev
, struct cds_list_head
* next
)
799 * cds_list_del - deletes entry from list.
800 * @entry: the element to delete from the list.
801 * Note: cds_list_empty() on entry does not return true after this, the entry is
802 * in an undefined state.
804 #ifndef CONFIG_DEBUG_LIST
805 static inline void cds_list_del(struct cds_list_head
*entry
)
807 __cds_list_del(entry
->prev
, entry
->next
);
808 entry
->next
= LIST_POISON1
;
809 entry
->prev
= LIST_POISON2
;
812 extern void cds_list_del(struct cds_list_head
*entry
);
816 * cds_list_replace - replace old entry by new one
817 * @old : the element to be replaced
818 * @new : the new element to insert
820 * If @old was empty, it will be overwritten.
822 static inline void cds_list_replace(struct cds_list_head
*old
,
823 struct cds_list_head
*new)
825 new->next
= old
->next
;
826 new->next
->prev
= new;
827 new->prev
= old
->prev
;
828 new->prev
->next
= new;
831 static inline void cds_list_replace_init(struct cds_list_head
*old
,
832 struct cds_list_head
*new)
834 cds_list_replace(old
, new);
835 CDS_INIT_LIST_HEAD(old
);
839 * cds_list_del_init - deletes entry from list and reinitialize it.
840 * @entry: the element to delete from the list.
842 static inline void cds_list_del_init(struct cds_list_head
*entry
)
844 __cds_list_del(entry
->prev
, entry
->next
);
845 CDS_INIT_LIST_HEAD(entry
);
849 * cds_list_move - delete from one list and add as another's head
850 * @list: the entry to move
851 * @head: the head that will precede our entry
853 static inline void cds_list_move(struct cds_list_head
*list
, struct cds_list_head
*head
)
855 __cds_list_del(list
->prev
, list
->next
);
856 cds_list_add(list
, head
);
860 * cds_list_move_tail - delete from one list and add as another's tail
861 * @list: the entry to move
862 * @head: the head that will follow our entry
864 static inline void cds_list_move_tail(struct cds_list_head
*list
,
865 struct cds_list_head
*head
)
867 __cds_list_del(list
->prev
, list
->next
);
868 cds_list_add_tail(list
, head
);
872 * list_is_last - tests whether @list is the last entry in list @head
873 * @list: the entry to test
874 * @head: the head of the list
876 static inline int list_is_last(const struct cds_list_head
*list
,
877 const struct cds_list_head
*head
)
879 return list
->next
== head
;
883 * cds_list_empty - tests whether a list is empty
884 * @head: the list to test.
886 static inline int cds_list_empty(const struct cds_list_head
*head
)
888 return head
->next
== head
;
892 * cds_list_empty_careful - tests whether a list is empty and not being modified
893 * @head: the list to test
896 * tests whether a list is empty _and_ checks that no other CPU might be
897 * in the process of modifying either member (next or prev)
899 * NOTE: using cds_list_empty_careful() without synchronization
900 * can only be safe if the only activity that can happen
901 * to the list entry is cds_list_del_init(). Eg. it cannot be used
902 * if another CPU could re-list_add() it.
904 static inline int cds_list_empty_careful(const struct cds_list_head
*head
)
906 struct cds_list_head
*next
= head
->next
;
907 return (next
== head
) && (next
== head
->prev
);
911 * list_is_singular - tests whether a list has just one entry.
912 * @head: the list to test.
914 static inline int list_is_singular(const struct cds_list_head
*head
)
916 return !list_empty(head
) && (head
->next
== head
->prev
);
919 static inline void __list_cut_position(struct cds_list_head
*list
,
920 struct cds_list_head
*head
, struct cds_list_head
*entry
)
922 struct cds_list_head
*new_first
= entry
->next
;
923 list
->next
= head
->next
;
924 list
->next
->prev
= list
;
927 head
->next
= new_first
;
928 new_first
->prev
= head
;
932 * list_cut_position - cut a list into two
933 * @list: a new list to add all removed entries
934 * @head: a list with entries
935 * @entry: an entry within head, could be the head itself
936 * and if so we won't cut the list
938 * This helper moves the initial part of @head, up to and
939 * including @entry, from @head to @list. You should
940 * pass on @entry an element you know is on @head. @list
941 * should be an empty list or a list you do not care about
945 static inline void list_cut_position(struct cds_list_head
*list
,
946 struct cds_list_head
*head
, struct cds_list_head
*entry
)
948 if (cds_list_empty(head
))
950 if (list_is_singular(head
) &&
951 (head
->next
!= entry
&& head
!= entry
))
954 CDS_INIT_LIST_HEAD(list
);
956 __list_cut_position(list
, head
, entry
);
959 static inline void __cds_list_splice(const struct cds_list_head
*list
,
960 struct cds_list_head
*prev
,
961 struct cds_list_head
*next
)
963 struct cds_list_head
*first
= list
->next
;
964 struct cds_list_head
*last
= list
->prev
;
974 * cds_list_splice - join two lists, this is designed for stacks
975 * @list: the new list to add.
976 * @head: the place to add it in the first list.
978 static inline void cds_list_splice(const struct cds_list_head
*list
,
979 struct cds_list_head
*head
)
981 if (!cds_list_empty(list
))
982 __cds_list_splice(list
, head
, head
->next
);
986 * cds_list_splice_tail - join two lists, each list being a queue
987 * @list: the new list to add.
988 * @head: the place to add it in the first list.
990 static inline void cds_list_splice_tail(struct cds_list_head
*list
,
991 struct cds_list_head
*head
)
993 if (!cds_list_empty(list
))
994 __cds_list_splice(list
, head
->prev
, head
);
998 * cds_list_splice_init - join two lists and reinitialise the emptied list.
999 * @list: the new list to add.
1000 * @head: the place to add it in the first list.
1002 * The list at @list is reinitialised
1004 static inline void cds_list_splice_init(struct cds_list_head
*list
,
1005 struct cds_list_head
*head
)
1007 if (!cds_list_empty(list
)) {
1008 __cds_list_splice(list
, head
, head
->next
);
1009 CDS_INIT_LIST_HEAD(list
);
1014 * cds_list_splice_tail_init - join two lists and reinitialise the emptied list
1015 * @list: the new list to add.
1016 * @head: the place to add it in the first list.
1018 * Each of the lists is a queue.
1019 * The list at @list is reinitialised
1021 static inline void cds_list_splice_tail_init(struct cds_list_head
*list
,
1022 struct cds_list_head
*head
)
1024 if (!cds_list_empty(list
)) {
1025 __cds_list_splice(list
, head
->prev
, head
);
1026 CDS_INIT_LIST_HEAD(list
);
1031 * cds_list_entry - get the struct for this entry
1032 * @ptr: the &struct cds_list_head pointer.
1033 * @type: the type of the struct this is embedded in.
1034 * @member: the name of the list_struct within the struct.
1036 #define cds_list_entry(ptr, type, member) \
1037 caa_container_of(ptr, type, member)
1040 * list_first_entry - get the first element from a list
1041 * @ptr: the list head to take the element from.
1042 * @type: the type of the struct this is embedded in.
1043 * @member: the name of the list_struct within the struct.
1045 * Note, that list is expected to be not empty.
1047 #define list_first_entry(ptr, type, member) \
1048 cds_list_entry((ptr)->next, type, member)
1051 * cds_list_for_each - iterate over a list
1052 * @pos: the &struct cds_list_head to use as a loop cursor.
1053 * @head: the head for your list.
1055 #define cds_list_for_each(pos, head) \
1056 for (pos = (head)->next; prefetch(pos->next), pos != (head); \
1060 * __cds_list_for_each - iterate over a list
1061 * @pos: the &struct cds_list_head to use as a loop cursor.
1062 * @head: the head for your list.
1064 * This variant differs from cds_list_for_each() in that it's the
1065 * simplest possible list iteration code, no prefetching is done.
1066 * Use this for code that knows the list to be very short (empty
1067 * or 1 entry) most of the time.
1069 #define __cds_list_for_each(pos, head) \
1070 for (pos = (head)->next; pos != (head); pos = pos->next)
1073 * cds_list_for_each_prev - iterate over a list backwards
1074 * @pos: the &struct cds_list_head to use as a loop cursor.
1075 * @head: the head for your list.
1077 #define cds_list_for_each_prev(pos, head) \
1078 for (pos = (head)->prev; prefetch(pos->prev), pos != (head); \
1082 * cds_list_for_each_safe - iterate over a list safe against removal of list entry
1083 * @pos: the &struct cds_list_head to use as a loop cursor.
1084 * @n: another &struct cds_list_head to use as temporary storage
1085 * @head: the head for your list.
1087 #define cds_list_for_each_safe(pos, n, head) \
1088 for (pos = (head)->next, n = pos->next; pos != (head); \
1089 pos = n, n = pos->next)
1092 * cds_list_for_each_prev_safe - iterate over a list backwards safe against removal of list entry
1093 * @pos: the &struct cds_list_head to use as a loop cursor.
1094 * @n: another &struct cds_list_head to use as temporary storage
1095 * @head: the head for your list.
1097 #define cds_list_for_each_prev_safe(pos, n, head) \
1098 for (pos = (head)->prev, n = pos->prev; \
1099 prefetch(pos->prev), pos != (head); \
1100 pos = n, n = pos->prev)
1103 * cds_list_for_each_entry - iterate over list of given type
1104 * @pos: the type * to use as a loop cursor.
1105 * @head: the head for your list.
1106 * @member: the name of the list_struct within the struct.
1108 #define cds_list_for_each_entry(pos, head, member) \
1109 for (pos = cds_list_entry((head)->next, typeof(*pos), member); \
1110 prefetch(pos->member.next), &pos->member != (head); \
1111 pos = cds_list_entry(pos->member.next, typeof(*pos), member))
1114 * cds_list_for_each_entry_reverse - iterate backwards over list of given type.
1115 * @pos: the type * to use as a loop cursor.
1116 * @head: the head for your list.
1117 * @member: the name of the list_struct within the struct.
1119 #define cds_list_for_each_entry_reverse(pos, head, member) \
1120 for (pos = cds_list_entry((head)->prev, typeof(*pos), member); \
1121 prefetch(pos->member.prev), &pos->member != (head); \
1122 pos = cds_list_entry(pos->member.prev, typeof(*pos), member))
1125 * list_prepare_entry - prepare a pos entry for use in cds_list_for_each_entry_continue()
1126 * @pos: the type * to use as a start point
1127 * @head: the head of the list
1128 * @member: the name of the list_struct within the struct.
1130 * Prepares a pos entry for use as a start point in cds_list_for_each_entry_continue().
1132 #define list_prepare_entry(pos, head, member) \
1133 ((pos) ? : cds_list_entry(head, typeof(*pos), member))
1136 * cds_list_for_each_entry_continue - continue iteration over list of given type
1137 * @pos: the type * to use as a loop cursor.
1138 * @head: the head for your list.
1139 * @member: the name of the list_struct within the struct.
1141 * Continue to iterate over list of given type, continuing after
1142 * the current position.
1144 #define cds_list_for_each_entry_continue(pos, head, member) \
1145 for (pos = cds_list_entry(pos->member.next, typeof(*pos), member); \
1146 prefetch(pos->member.next), &pos->member != (head); \
1147 pos = cds_list_entry(pos->member.next, typeof(*pos), member))
1150 * cds_list_for_each_entry_continue_reverse - iterate backwards from the given point
1151 * @pos: the type * to use as a loop cursor.
1152 * @head: the head for your list.
1153 * @member: the name of the list_struct within the struct.
1155 * Start to iterate over list of given type backwards, continuing after
1156 * the current position.
1158 #define cds_list_for_each_entry_continue_reverse(pos, head, member) \
1159 for (pos = cds_list_entry(pos->member.prev, typeof(*pos), member); \
1160 prefetch(pos->member.prev), &pos->member != (head); \
1161 pos = cds_list_entry(pos->member.prev, typeof(*pos), member))
1164 * cds_list_for_each_entry_from - iterate over list of given type from the current point
1165 * @pos: the type * to use as a loop cursor.
1166 * @head: the head for your list.
1167 * @member: the name of the list_struct within the struct.
1169 * Iterate over list of given type, continuing from current position.
1171 #define cds_list_for_each_entry_from(pos, head, member) \
1172 for (; prefetch(pos->member.next), &pos->member != (head); \
1173 pos = cds_list_entry(pos->member.next, typeof(*pos), member))
1176 * cds_list_for_each_entry_safe - iterate over list of given type safe against removal of list entry
1177 * @pos: the type * to use as a loop cursor.
1178 * @n: another type * to use as temporary storage
1179 * @head: the head for your list.
1180 * @member: the name of the list_struct within the struct.
1182 #define cds_list_for_each_entry_safe(pos, n, head, member) \
1183 for (pos = cds_list_entry((head)->next, typeof(*pos), member), \
1184 n = cds_list_entry(pos->member.next, typeof(*pos), member); \
1185 &pos->member != (head); \
1186 pos = n, n = cds_list_entry(n->member.next, typeof(*n), member))
1189 * cds_list_for_each_entry_safe_continue
1190 * @pos: the type * to use as a loop cursor.
1191 * @n: another type * to use as temporary storage
1192 * @head: the head for your list.
1193 * @member: the name of the list_struct within the struct.
1195 * Iterate over list of given type, continuing after current point,
1196 * safe against removal of list entry.
1198 #define cds_list_for_each_entry_safe_continue(pos, n, head, member) \
1199 for (pos = cds_list_entry(pos->member.next, typeof(*pos), member), \
1200 n = cds_list_entry(pos->member.next, typeof(*pos), member); \
1201 &pos->member != (head); \
1202 pos = n, n = cds_list_entry(n->member.next, typeof(*n), member))
1205 * cds_list_for_each_entry_safe_from
1206 * @pos: the type * to use as a loop cursor.
1207 * @n: another type * to use as temporary storage
1208 * @head: the head for your list.
1209 * @member: the name of the list_struct within the struct.
1211 * Iterate over list of given type from current point, safe against
1212 * removal of list entry.
1214 #define cds_list_for_each_entry_safe_from(pos, n, head, member) \
1215 for (n = cds_list_entry(pos->member.next, typeof(*pos), member); \
1216 &pos->member != (head); \
1217 pos = n, n = cds_list_entry(n->member.next, typeof(*n), member))
1220 * cds_list_for_each_entry_safe_reverse
1221 * @pos: the type * to use as a loop cursor.
1222 * @n: another type * to use as temporary storage
1223 * @head: the head for your list.
1224 * @member: the name of the list_struct within the struct.
1226 * Iterate backwards over list of given type, safe against removal
1229 #define cds_list_for_each_entry_safe_reverse(pos, n, head, member) \
1230 for (pos = cds_list_entry((head)->prev, typeof(*pos), member), \
1231 n = cds_list_entry(pos->member.prev, typeof(*pos), member); \
1232 &pos->member != (head); \
1233 pos = n, n = cds_list_entry(n->member.prev, typeof(*n), member))
1238 * Double linked lists with a single pointer list head.
1239 * Mostly useful for hash tables where the two pointer list head is
1241 * You lose the ability to access the tail in O(1).
1244 struct cds_hlist_head
{
1245 struct cds_hlist_node
*first
;
1248 struct cds_hlist_node
{
1249 struct cds_hlist_node
*next
, **pprev
;
1252 #define HLIST_HEAD_INIT { .first = NULL }
1253 #define HLIST_HEAD(name) struct cds_hlist_head name = { .first = NULL }
1254 #define CDS_INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL)
1255 static inline void INIT_HLIST_NODE(struct cds_hlist_node
*h
)
1261 static inline int hlist_unhashed(const struct cds_hlist_node
*h
)
1266 static inline int hlist_empty(const struct cds_hlist_head
*h
)
1271 static inline void __cds_hlist_del(struct cds_hlist_node
*n
)
1273 struct cds_hlist_node
*next
= n
->next
;
1274 struct cds_hlist_node
**pprev
= n
->pprev
;
1277 next
->pprev
= pprev
;
1280 static inline void cds_hlist_del(struct cds_hlist_node
*n
)
1283 n
->next
= LIST_POISON1
;
1284 n
->pprev
= LIST_POISON2
;
1287 static inline void cds_hlist_del_init(struct cds_hlist_node
*n
)
1289 if (!hlist_unhashed(n
)) {
1295 static inline void cds_hlist_add_head(struct cds_hlist_node
*n
, struct cds_hlist_head
*h
)
1297 struct cds_hlist_node
*first
= h
->first
;
1300 first
->pprev
= &n
->next
;
1302 n
->pprev
= &h
->first
;
1305 /* next must be != NULL */
1306 static inline void hlist_add_before(struct cds_hlist_node
*n
,
1307 struct cds_hlist_node
*next
)
1309 n
->pprev
= next
->pprev
;
1311 next
->pprev
= &n
->next
;
1315 static inline void hlist_add_after(struct cds_hlist_node
*n
,
1316 struct cds_hlist_node
*next
)
1318 next
->next
= n
->next
;
1320 next
->pprev
= &n
->next
;
1323 next
->next
->pprev
= &next
->next
;
1327 * Move a list from one list head to another. Fixup the pprev
1328 * reference of the first entry if it exists.
1330 static inline void hlist_move_list(struct cds_hlist_head
*old
,
1331 struct cds_hlist_head
*new)
1333 new->first
= old
->first
;
1335 new->first
->pprev
= &new->first
;
1339 #define cds_hlist_entry(ptr, type, member) caa_container_of(ptr,type,member)
1341 #define cds_hlist_for_each(pos, head) \
1342 for (pos = (head)->first; pos && ({ prefetch(pos->next); 1; }); \
1345 #define cds_hlist_for_each_safe(pos, n, head) \
1346 for (pos = (head)->first; pos && ({ n = pos->next; 1; }); \
1350 * cds_hlist_for_each_entry - iterate over list of given type
1351 * @tpos: the type * to use as a loop cursor.
1352 * @pos: the &struct cds_hlist_node to use as a loop cursor.
1353 * @head: the head for your list.
1354 * @member: the name of the cds_hlist_node within the struct.
1356 #define cds_hlist_for_each_entry(tpos, pos, head, member) \
1357 for (pos = (head)->first; \
1358 pos && ({ prefetch(pos->next); 1;}) && \
1359 ({ tpos = cds_hlist_entry(pos, typeof(*tpos), member); 1;}); \
1363 * cds_hlist_for_each_entry_continue - iterate over a hlist continuing after current point
1364 * @tpos: the type * to use as a loop cursor.
1365 * @pos: the &struct cds_hlist_node to use as a loop cursor.
1366 * @member: the name of the cds_hlist_node within the struct.
1368 #define cds_hlist_for_each_entry_continue(tpos, pos, member) \
1369 for (pos = (pos)->next; \
1370 pos && ({ prefetch(pos->next); 1;}) && \
1371 ({ tpos = cds_hlist_entry(pos, typeof(*tpos), member); 1;}); \
1375 * cds_hlist_for_each_entry_from - iterate over a hlist continuing from current point
1376 * @tpos: the type * to use as a loop cursor.
1377 * @pos: the &struct cds_hlist_node to use as a loop cursor.
1378 * @member: the name of the cds_hlist_node within the struct.
1380 #define cds_hlist_for_each_entry_from(tpos, pos, member) \
1381 for (; pos && ({ prefetch(pos->next); 1;}) && \
1382 ({ tpos = cds_hlist_entry(pos, typeof(*tpos), member); 1;}); \
1386 * cds_hlist_for_each_entry_safe - iterate over list of given type safe against removal of list entry
1387 * @tpos: the type * to use as a loop cursor.
1388 * @pos: the &struct cds_hlist_node to use as a loop cursor.
1389 * @n: another &struct cds_hlist_node to use as temporary storage
1390 * @head: the head for your list.
1391 * @member: the name of the cds_hlist_node within the struct.
1393 #define cds_hlist_for_each_entry_safe(tpos, pos, n, head, member) \
1394 for (pos = (head)->first; \
1395 pos && ({ n = pos->next; 1; }) && \
1396 ({ tpos = cds_hlist_entry(pos, typeof(*tpos), member); 1;}); \