Subversion Repositories Kolibri OS

Rev

Rev 4065 | Rev 5056 | Go to most recent revision | Details | Compare with Previous | Last modification | View Log | RSS feed

Rev Author Line No. Line
4065 Serge 1
#ifndef _LINUX_RCULIST_H
2
#define _LINUX_RCULIST_H
3
 
4
#ifdef __KERNEL__
5
 
6
/*
7
 * RCU-protected list version
8
 */
9
#include 
10
//#include 
11
 
12
/*
13
 * Why is there no list_empty_rcu()?  Because list_empty() serves this
14
 * purpose.  The list_empty() function fetches the RCU-protected pointer
15
 * and compares it to the address of the list head, but neither dereferences
16
 * this pointer itself nor provides this pointer to the caller.  Therefore,
17
 * it is not necessary to use rcu_dereference(), so that list_empty() can
18
 * be used anywhere you would want to use a list_empty_rcu().
19
 */
20
 
21
/*
22
 * return the ->next pointer of a list_head in an rcu safe
23
 * way, we must not access it directly
24
 */
25
#define list_next_rcu(list)	(*((struct list_head __rcu **)(&(list)->next)))
26
 
27
/*
28
 * Insert a new entry between two known consecutive entries.
29
 *
30
 * This is only for internal list manipulation where we know
31
 * the prev/next entries already!
32
 */
33
#ifndef CONFIG_DEBUG_LIST
34
static inline void __list_add_rcu(struct list_head *new,
35
		struct list_head *prev, struct list_head *next)
36
{
37
	new->next = next;
38
	new->prev = prev;
39
	rcu_assign_pointer(list_next_rcu(prev), new);
40
	next->prev = new;
41
}
42
#else
43
extern void __list_add_rcu(struct list_head *new,
44
		struct list_head *prev, struct list_head *next);
45
#endif
46
 
47
/**
48
 * list_add_rcu - add a new entry to rcu-protected list
49
 * @new: new entry to be added
50
 * @head: list head to add it after
51
 *
52
 * Insert a new entry after the specified head.
53
 * This is good for implementing stacks.
54
 *
55
 * The caller must take whatever precautions are necessary
56
 * (such as holding appropriate locks) to avoid racing
57
 * with another list-mutation primitive, such as list_add_rcu()
58
 * or list_del_rcu(), running on this same list.
59
 * However, it is perfectly legal to run concurrently with
60
 * the _rcu list-traversal primitives, such as
61
 * list_for_each_entry_rcu().
62
 */
63
static inline void list_add_rcu(struct list_head *new, struct list_head *head)
64
{
65
	__list_add_rcu(new, head, head->next);
66
}
67
 
68
/**
69
 * list_add_tail_rcu - add a new entry to rcu-protected list
70
 * @new: new entry to be added
71
 * @head: list head to add it before
72
 *
73
 * Insert a new entry before the specified head.
74
 * This is useful for implementing queues.
75
 *
76
 * The caller must take whatever precautions are necessary
77
 * (such as holding appropriate locks) to avoid racing
78
 * with another list-mutation primitive, such as list_add_tail_rcu()
79
 * or list_del_rcu(), running on this same list.
80
 * However, it is perfectly legal to run concurrently with
81
 * the _rcu list-traversal primitives, such as
82
 * list_for_each_entry_rcu().
83
 */
84
static inline void list_add_tail_rcu(struct list_head *new,
85
					struct list_head *head)
86
{
87
	__list_add_rcu(new, head->prev, head);
88
}
89
 
90
/**
91
 * list_del_rcu - deletes entry from list without re-initialization
92
 * @entry: the element to delete from the list.
93
 *
94
 * Note: list_empty() on entry does not return true after this,
95
 * the entry is in an undefined state. It is useful for RCU based
96
 * lockfree traversal.
97
 *
98
 * In particular, it means that we can not poison the forward
99
 * pointers that may still be used for walking the list.
100
 *
101
 * The caller must take whatever precautions are necessary
102
 * (such as holding appropriate locks) to avoid racing
103
 * with another list-mutation primitive, such as list_del_rcu()
104
 * or list_add_rcu(), running on this same list.
105
 * However, it is perfectly legal to run concurrently with
106
 * the _rcu list-traversal primitives, such as
107
 * list_for_each_entry_rcu().
108
 *
109
 * Note that the caller is not permitted to immediately free
110
 * the newly deleted entry.  Instead, either synchronize_rcu()
111
 * or call_rcu() must be used to defer freeing until an RCU
112
 * grace period has elapsed.
113
 */
114
static inline void list_del_rcu(struct list_head *entry)
115
{
116
	__list_del_entry(entry);
117
	entry->prev = LIST_POISON2;
118
}
119
 
120
/**
121
 * hlist_del_init_rcu - deletes entry from hash list with re-initialization
122
 * @n: the element to delete from the hash list.
123
 *
124
 * Note: list_unhashed() on the node return true after this. It is
125
 * useful for RCU based read lockfree traversal if the writer side
126
 * must know if the list entry is still hashed or already unhashed.
127
 *
128
 * In particular, it means that we can not poison the forward pointers
129
 * that may still be used for walking the hash list and we can only
130
 * zero the pprev pointer so list_unhashed() will return true after
131
 * this.
132
 *
133
 * The caller must take whatever precautions are necessary (such as
134
 * holding appropriate locks) to avoid racing with another
135
 * list-mutation primitive, such as hlist_add_head_rcu() or
136
 * hlist_del_rcu(), running on this same list.  However, it is
137
 * perfectly legal to run concurrently with the _rcu list-traversal
138
 * primitives, such as hlist_for_each_entry_rcu().
139
 */
140
static inline void hlist_del_init_rcu(struct hlist_node *n)
141
{
142
	if (!hlist_unhashed(n)) {
143
		__hlist_del(n);
144
		n->pprev = NULL;
145
	}
146
}
147
 
148
/**
149
 * list_replace_rcu - replace old entry by new one
150
 * @old : the element to be replaced
151
 * @new : the new element to insert
152
 *
153
 * The @old entry will be replaced with the @new entry atomically.
154
 * Note: @old should not be empty.
155
 */
156
static inline void list_replace_rcu(struct list_head *old,
157
				struct list_head *new)
158
{
159
	new->next = old->next;
160
	new->prev = old->prev;
161
	rcu_assign_pointer(list_next_rcu(new->prev), new);
162
	new->next->prev = new;
163
	old->prev = LIST_POISON2;
164
}
165
 
166
/**
167
 * list_splice_init_rcu - splice an RCU-protected list into an existing list.
168
 * @list:	the RCU-protected list to splice
169
 * @head:	the place in the list to splice the first list into
170
 * @sync:	function to sync: synchronize_rcu(), synchronize_sched(), ...
171
 *
172
 * @head can be RCU-read traversed concurrently with this function.
173
 *
174
 * Note that this function blocks.
175
 *
176
 * Important note: the caller must take whatever action is necessary to
177
 *	prevent any other updates to @head.  In principle, it is possible
178
 *	to modify the list as soon as sync() begins execution.
179
 *	If this sort of thing becomes necessary, an alternative version
180
 *	based on call_rcu() could be created.  But only if -really-
181
 *	needed -- there is no shortage of RCU API members.
182
 */
183
static inline void list_splice_init_rcu(struct list_head *list,
184
					struct list_head *head,
185
					void (*sync)(void))
186
{
187
	struct list_head *first = list->next;
188
	struct list_head *last = list->prev;
189
	struct list_head *at = head->next;
190
 
191
	if (list_empty(list))
192
		return;
193
 
194
	/* "first" and "last" tracking list, so initialize it. */
195
 
196
	INIT_LIST_HEAD(list);
197
 
198
	/*
199
	 * At this point, the list body still points to the source list.
200
	 * Wait for any readers to finish using the list before splicing
201
	 * the list body into the new list.  Any new readers will see
202
	 * an empty list.
203
	 */
204
 
205
	sync();
206
 
207
	/*
208
	 * Readers are finished with the source list, so perform splice.
209
	 * The order is important if the new list is global and accessible
210
	 * to concurrent RCU readers.  Note that RCU readers are not
211
	 * permitted to traverse the prev pointers without excluding
212
	 * this function.
213
	 */
214
 
215
	last->next = at;
216
	rcu_assign_pointer(list_next_rcu(head), first);
217
	first->prev = head;
218
	at->prev = last;
219
}
220
 
221
/**
222
 * list_entry_rcu - get the struct for this entry
223
 * @ptr:        the &struct list_head pointer.
224
 * @type:       the type of the struct this is embedded in.
225
 * @member:     the name of the list_struct within the struct.
226
 *
227
 * This primitive may safely run concurrently with the _rcu list-mutation
228
 * primitives such as list_add_rcu() as long as it's guarded by rcu_read_lock().
229
 */
230
#define list_entry_rcu(ptr, type, member) \
231
	({typeof (*ptr) __rcu *__ptr = (typeof (*ptr) __rcu __force *)ptr; \
232
	 container_of((typeof(ptr))rcu_dereference_raw(__ptr), type, member); \
233
	})
234
 
235
/**
236
 * Where are list_empty_rcu() and list_first_entry_rcu()?
237
 *
238
 * Implementing those functions following their counterparts list_empty() and
239
 * list_first_entry() is not advisable because they lead to subtle race
240
 * conditions as the following snippet shows:
241
 *
242
 * if (!list_empty_rcu(mylist)) {
243
 *	struct foo *bar = list_first_entry_rcu(mylist, struct foo, list_member);
244
 *	do_something(bar);
245
 * }
246
 *
247
 * The list may not be empty when list_empty_rcu checks it, but it may be when
248
 * list_first_entry_rcu rereads the ->next pointer.
249
 *
250
 * Rereading the ->next pointer is not a problem for list_empty() and
251
 * list_first_entry() because they would be protected by a lock that blocks
252
 * writers.
253
 *
254
 * See list_first_or_null_rcu for an alternative.
255
 */
256
 
257
/**
258
 * list_first_or_null_rcu - get the first element from a list
259
 * @ptr:        the list head to take the element from.
260
 * @type:       the type of the struct this is embedded in.
261
 * @member:     the name of the list_struct within the struct.
262
 *
263
 * Note that if the list is empty, it returns NULL.
264
 *
265
 * This primitive may safely run concurrently with the _rcu list-mutation
266
 * primitives such as list_add_rcu() as long as it's guarded by rcu_read_lock().
267
 */
268
#define list_first_or_null_rcu(ptr, type, member) \
269
	({struct list_head *__ptr = (ptr); \
4103 Serge 270
	  struct list_head *__next = ACCESS_ONCE(__ptr->next); \
271
	  likely(__ptr != __next) ? \
272
		list_entry_rcu(__next, type, member) : NULL; \
4065 Serge 273
	})
274
 
275
/**
276
 * list_for_each_entry_rcu	-	iterate over rcu list of given type
277
 * @pos:	the type * to use as a loop cursor.
278
 * @head:	the head for your list.
279
 * @member:	the name of the list_struct within the struct.
280
 *
281
 * This list-traversal primitive may safely run concurrently with
282
 * the _rcu list-mutation primitives such as list_add_rcu()
283
 * as long as the traversal is guarded by rcu_read_lock().
284
 */
285
#define list_for_each_entry_rcu(pos, head, member) \
286
	for (pos = list_entry_rcu((head)->next, typeof(*pos), member); \
287
		&pos->member != (head); \
288
		pos = list_entry_rcu(pos->member.next, typeof(*pos), member))
289
 
290
/**
291
 * list_for_each_entry_continue_rcu - continue iteration over list of given type
292
 * @pos:	the type * to use as a loop cursor.
293
 * @head:	the head for your list.
294
 * @member:	the name of the list_struct within the struct.
295
 *
296
 * Continue to iterate over list of given type, continuing after
297
 * the current position.
298
 */
299
#define list_for_each_entry_continue_rcu(pos, head, member) 		\
300
	for (pos = list_entry_rcu(pos->member.next, typeof(*pos), member); \
301
	     &pos->member != (head);	\
302
	     pos = list_entry_rcu(pos->member.next, typeof(*pos), member))
303
 
304
/**
305
 * hlist_del_rcu - deletes entry from hash list without re-initialization
306
 * @n: the element to delete from the hash list.
307
 *
308
 * Note: list_unhashed() on entry does not return true after this,
309
 * the entry is in an undefined state. It is useful for RCU based
310
 * lockfree traversal.
311
 *
312
 * In particular, it means that we can not poison the forward
313
 * pointers that may still be used for walking the hash list.
314
 *
315
 * The caller must take whatever precautions are necessary
316
 * (such as holding appropriate locks) to avoid racing
317
 * with another list-mutation primitive, such as hlist_add_head_rcu()
318
 * or hlist_del_rcu(), running on this same list.
319
 * However, it is perfectly legal to run concurrently with
320
 * the _rcu list-traversal primitives, such as
321
 * hlist_for_each_entry().
322
 */
323
static inline void hlist_del_rcu(struct hlist_node *n)
324
{
325
	__hlist_del(n);
326
	n->pprev = LIST_POISON2;
327
}
328
 
329
/**
330
 * hlist_replace_rcu - replace old entry by new one
331
 * @old : the element to be replaced
332
 * @new : the new element to insert
333
 *
334
 * The @old entry will be replaced with the @new entry atomically.
335
 */
336
static inline void hlist_replace_rcu(struct hlist_node *old,
337
					struct hlist_node *new)
338
{
339
	struct hlist_node *next = old->next;
340
 
341
	new->next = next;
342
	new->pprev = old->pprev;
343
	rcu_assign_pointer(*(struct hlist_node __rcu **)new->pprev, new);
344
	if (next)
345
		new->next->pprev = &new->next;
346
	old->pprev = LIST_POISON2;
347
}
348
 
349
/*
350
 * return the first or the next element in an RCU protected hlist
351
 */
352
#define hlist_first_rcu(head)	(*((struct hlist_node __rcu **)(&(head)->first)))
353
#define hlist_next_rcu(node)	(*((struct hlist_node __rcu **)(&(node)->next)))
354
#define hlist_pprev_rcu(node)	(*((struct hlist_node __rcu **)((node)->pprev)))
355
 
356
/**
357
 * hlist_add_head_rcu
358
 * @n: the element to add to the hash list.
359
 * @h: the list to add to.
360
 *
361
 * Description:
362
 * Adds the specified element to the specified hlist,
363
 * while permitting racing traversals.
364
 *
365
 * The caller must take whatever precautions are necessary
366
 * (such as holding appropriate locks) to avoid racing
367
 * with another list-mutation primitive, such as hlist_add_head_rcu()
368
 * or hlist_del_rcu(), running on this same list.
369
 * However, it is perfectly legal to run concurrently with
370
 * the _rcu list-traversal primitives, such as
371
 * hlist_for_each_entry_rcu(), used to prevent memory-consistency
372
 * problems on Alpha CPUs.  Regardless of the type of CPU, the
373
 * list-traversal primitive must be guarded by rcu_read_lock().
374
 */
375
static inline void hlist_add_head_rcu(struct hlist_node *n,
376
					struct hlist_head *h)
377
{
378
	struct hlist_node *first = h->first;
379
 
380
	n->next = first;
381
	n->pprev = &h->first;
382
	rcu_assign_pointer(hlist_first_rcu(h), n);
383
	if (first)
384
		first->pprev = &n->next;
385
}
386
 
387
/**
388
 * hlist_add_before_rcu
389
 * @n: the new element to add to the hash list.
390
 * @next: the existing element to add the new element before.
391
 *
392
 * Description:
393
 * Adds the specified element to the specified hlist
394
 * before the specified node while permitting racing traversals.
395
 *
396
 * The caller must take whatever precautions are necessary
397
 * (such as holding appropriate locks) to avoid racing
398
 * with another list-mutation primitive, such as hlist_add_head_rcu()
399
 * or hlist_del_rcu(), running on this same list.
400
 * However, it is perfectly legal to run concurrently with
401
 * the _rcu list-traversal primitives, such as
402
 * hlist_for_each_entry_rcu(), used to prevent memory-consistency
403
 * problems on Alpha CPUs.
404
 */
405
static inline void hlist_add_before_rcu(struct hlist_node *n,
406
					struct hlist_node *next)
407
{
408
	n->pprev = next->pprev;
409
	n->next = next;
410
	rcu_assign_pointer(hlist_pprev_rcu(n), n);
411
	next->pprev = &n->next;
412
}
413
 
414
/**
415
 * hlist_add_after_rcu
416
 * @prev: the existing element to add the new element after.
417
 * @n: the new element to add to the hash list.
418
 *
419
 * Description:
420
 * Adds the specified element to the specified hlist
421
 * after the specified node while permitting racing traversals.
422
 *
423
 * The caller must take whatever precautions are necessary
424
 * (such as holding appropriate locks) to avoid racing
425
 * with another list-mutation primitive, such as hlist_add_head_rcu()
426
 * or hlist_del_rcu(), running on this same list.
427
 * However, it is perfectly legal to run concurrently with
428
 * the _rcu list-traversal primitives, such as
429
 * hlist_for_each_entry_rcu(), used to prevent memory-consistency
430
 * problems on Alpha CPUs.
431
 */
432
static inline void hlist_add_after_rcu(struct hlist_node *prev,
433
				       struct hlist_node *n)
434
{
435
	n->next = prev->next;
436
	n->pprev = &prev->next;
437
	rcu_assign_pointer(hlist_next_rcu(prev), n);
438
	if (n->next)
439
		n->next->pprev = &n->next;
440
}
441
 
442
#define __hlist_for_each_rcu(pos, head)				\
443
	for (pos = rcu_dereference(hlist_first_rcu(head));	\
444
	     pos;						\
445
	     pos = rcu_dereference(hlist_next_rcu(pos)))
446
 
447
/**
448
 * hlist_for_each_entry_rcu - iterate over rcu list of given type
449
 * @pos:	the type * to use as a loop cursor.
450
 * @head:	the head for your list.
451
 * @member:	the name of the hlist_node within the struct.
452
 *
453
 * This list-traversal primitive may safely run concurrently with
454
 * the _rcu list-mutation primitives such as hlist_add_head_rcu()
455
 * as long as the traversal is guarded by rcu_read_lock().
456
 */
457
#define hlist_for_each_entry_rcu(pos, head, member)			\
458
	for (pos = hlist_entry_safe (rcu_dereference_raw(hlist_first_rcu(head)),\
459
			typeof(*(pos)), member);			\
460
		pos;							\
461
		pos = hlist_entry_safe(rcu_dereference_raw(hlist_next_rcu(\
462
			&(pos)->member)), typeof(*(pos)), member))
463
 
464
/**
465
 * hlist_for_each_entry_rcu_notrace - iterate over rcu list of given type (for tracing)
466
 * @pos:	the type * to use as a loop cursor.
467
 * @head:	the head for your list.
468
 * @member:	the name of the hlist_node within the struct.
469
 *
470
 * This list-traversal primitive may safely run concurrently with
471
 * the _rcu list-mutation primitives such as hlist_add_head_rcu()
472
 * as long as the traversal is guarded by rcu_read_lock().
473
 *
474
 * This is the same as hlist_for_each_entry_rcu() except that it does
475
 * not do any RCU debugging or tracing.
476
 */
477
#define hlist_for_each_entry_rcu_notrace(pos, head, member)			\
478
	for (pos = hlist_entry_safe (rcu_dereference_raw_notrace(hlist_first_rcu(head)),\
479
			typeof(*(pos)), member);			\
480
		pos;							\
481
		pos = hlist_entry_safe(rcu_dereference_raw_notrace(hlist_next_rcu(\
482
			&(pos)->member)), typeof(*(pos)), member))
483
 
484
/**
485
 * hlist_for_each_entry_rcu_bh - iterate over rcu list of given type
486
 * @pos:	the type * to use as a loop cursor.
487
 * @head:	the head for your list.
488
 * @member:	the name of the hlist_node within the struct.
489
 *
490
 * This list-traversal primitive may safely run concurrently with
491
 * the _rcu list-mutation primitives such as hlist_add_head_rcu()
492
 * as long as the traversal is guarded by rcu_read_lock().
493
 */
494
#define hlist_for_each_entry_rcu_bh(pos, head, member)			\
495
	for (pos = hlist_entry_safe(rcu_dereference_bh(hlist_first_rcu(head)),\
496
			typeof(*(pos)), member);			\
497
		pos;							\
498
		pos = hlist_entry_safe(rcu_dereference_bh(hlist_next_rcu(\
499
			&(pos)->member)), typeof(*(pos)), member))
500
 
501
/**
502
 * hlist_for_each_entry_continue_rcu - iterate over a hlist continuing after current point
503
 * @pos:	the type * to use as a loop cursor.
504
 * @member:	the name of the hlist_node within the struct.
505
 */
506
#define hlist_for_each_entry_continue_rcu(pos, member)			\
507
	for (pos = hlist_entry_safe(rcu_dereference((pos)->member.next),\
508
			typeof(*(pos)), member);			\
509
	     pos;							\
510
	     pos = hlist_entry_safe(rcu_dereference((pos)->member.next),\
511
			typeof(*(pos)), member))
512
 
513
/**
514
 * hlist_for_each_entry_continue_rcu_bh - iterate over a hlist continuing after current point
515
 * @pos:	the type * to use as a loop cursor.
516
 * @member:	the name of the hlist_node within the struct.
517
 */
518
#define hlist_for_each_entry_continue_rcu_bh(pos, member)		\
519
	for (pos = hlist_entry_safe(rcu_dereference_bh((pos)->member.next),\
520
			typeof(*(pos)), member);			\
521
	     pos;							\
522
	     pos = hlist_entry_safe(rcu_dereference_bh((pos)->member.next),\
523
			typeof(*(pos)), member))
524
 
525
 
526
#endif	/* __KERNEL__ */
527
#endif