aboutsummaryrefslogtreecommitdiffstats
path: root/fs/btrfs
diff options
context:
space:
mode:
Diffstat (limited to 'fs/btrfs')
-rw-r--r--fs/btrfs/ctree.c66
-rw-r--r--fs/btrfs/ctree.h5
-rw-r--r--fs/btrfs/disk-io.c91
-rw-r--r--fs/btrfs/disk-io.h6
-rw-r--r--fs/btrfs/list.h418
5 files changed, 558 insertions, 28 deletions
diff --git a/fs/btrfs/ctree.c b/fs/btrfs/ctree.c
index afa5bc5c7c1a..57fa505fb9f6 100644
--- a/fs/btrfs/ctree.c
+++ b/fs/btrfs/ctree.c
@@ -250,6 +250,7 @@ static int balance_level(struct ctree_root *root, struct ctree_path *path,
250 tree_block_release(root, mid_buf); 250 tree_block_release(root, mid_buf);
251 /* once for the root ptr */ 251 /* once for the root ptr */
252 tree_block_release(root, mid_buf); 252 tree_block_release(root, mid_buf);
253 clean_tree_block(root, mid_buf);
253 return free_extent(root, blocknr, 1); 254 return free_extent(root, blocknr, 1);
254 } 255 }
255 parent = &parent_buf->node; 256 parent = &parent_buf->node;
@@ -280,6 +281,7 @@ static int balance_level(struct ctree_root *root, struct ctree_path *path,
280 if (right->header.nritems == 0) { 281 if (right->header.nritems == 0) {
281 u64 blocknr = right_buf->blocknr; 282 u64 blocknr = right_buf->blocknr;
282 tree_block_release(root, right_buf); 283 tree_block_release(root, right_buf);
284 clean_tree_block(root, right_buf);
283 right_buf = NULL; 285 right_buf = NULL;
284 right = NULL; 286 right = NULL;
285 wret = del_ptr(root, path, level + 1, pslot + 1); 287 wret = del_ptr(root, path, level + 1, pslot + 1);
@@ -291,7 +293,7 @@ static int balance_level(struct ctree_root *root, struct ctree_path *path,
291 } else { 293 } else {
292 memcpy(parent->keys + pslot + 1, right->keys, 294 memcpy(parent->keys + pslot + 1, right->keys,
293 sizeof(struct key)); 295 sizeof(struct key));
294 wret = write_tree_block(root, parent_buf); 296 wret = dirty_tree_block(root, parent_buf);
295 if (wret) 297 if (wret)
296 ret = wret; 298 ret = wret;
297 } 299 }
@@ -316,6 +318,7 @@ static int balance_level(struct ctree_root *root, struct ctree_path *path,
316 /* we've managed to empty the middle node, drop it */ 318 /* we've managed to empty the middle node, drop it */
317 u64 blocknr = mid_buf->blocknr; 319 u64 blocknr = mid_buf->blocknr;
318 tree_block_release(root, mid_buf); 320 tree_block_release(root, mid_buf);
321 clean_tree_block(root, mid_buf);
319 mid_buf = NULL; 322 mid_buf = NULL;
320 mid = NULL; 323 mid = NULL;
321 wret = del_ptr(root, path, level + 1, pslot); 324 wret = del_ptr(root, path, level + 1, pslot);
@@ -327,7 +330,7 @@ static int balance_level(struct ctree_root *root, struct ctree_path *path,
327 } else { 330 } else {
328 /* update the parent key to reflect our changes */ 331 /* update the parent key to reflect our changes */
329 memcpy(parent->keys + pslot, mid->keys, sizeof(struct key)); 332 memcpy(parent->keys + pslot, mid->keys, sizeof(struct key));
330 wret = write_tree_block(root, parent_buf); 333 wret = dirty_tree_block(root, parent_buf);
331 if (wret) 334 if (wret)
332 ret = wret; 335 ret = wret;
333 } 336 }
@@ -458,7 +461,7 @@ static int fixup_low_keys(struct ctree_root *root,
458 break; 461 break;
459 t = &path->nodes[i]->node; 462 t = &path->nodes[i]->node;
460 memcpy(t->keys + tslot, key, sizeof(*key)); 463 memcpy(t->keys + tslot, key, sizeof(*key));
461 wret = write_tree_block(root, path->nodes[i]); 464 wret = dirty_tree_block(root, path->nodes[i]);
462 if (wret) 465 if (wret)
463 ret = wret; 466 ret = wret;
464 if (tslot != 0) 467 if (tslot != 0)
@@ -508,11 +511,11 @@ static int push_node_left(struct ctree_root *root, struct tree_buffer *dst_buf,
508 src->header.nritems -= push_items; 511 src->header.nritems -= push_items;
509 dst->header.nritems += push_items; 512 dst->header.nritems += push_items;
510 513
511 wret = write_tree_block(root, src_buf); 514 wret = dirty_tree_block(root, src_buf);
512 if (wret < 0) 515 if (wret < 0)
513 ret = wret; 516 ret = wret;
514 517
515 wret = write_tree_block(root, dst_buf); 518 wret = dirty_tree_block(root, dst_buf);
516 if (wret < 0) 519 if (wret < 0)
517 ret = wret; 520 ret = wret;
518 return ret; 521 return ret;
@@ -566,11 +569,11 @@ static int balance_node_right(struct ctree_root *root,
566 src->header.nritems -= push_items; 569 src->header.nritems -= push_items;
567 dst->header.nritems += push_items; 570 dst->header.nritems += push_items;
568 571
569 wret = write_tree_block(root, src_buf); 572 wret = dirty_tree_block(root, src_buf);
570 if (wret < 0) 573 if (wret < 0)
571 ret = wret; 574 ret = wret;
572 575
573 wret = write_tree_block(root, dst_buf); 576 wret = dirty_tree_block(root, dst_buf);
574 if (wret < 0) 577 if (wret < 0)
575 ret = wret; 578 ret = wret;
576 return ret; 579 return ret;
@@ -612,7 +615,7 @@ static int insert_new_root(struct ctree_root *root,
612 tree_block_release(root, root->node); 615 tree_block_release(root, root->node);
613 root->node = t; 616 root->node = t;
614 t->count++; 617 t->count++;
615 write_tree_block(root, t); 618 dirty_tree_block(root, t);
616 path->nodes[level] = t; 619 path->nodes[level] = t;
617 path->slots[level] = 0; 620 path->slots[level] = 0;
618 return 0; 621 return 0;
@@ -652,7 +655,7 @@ static int insert_ptr(struct ctree_root *root,
652 lower->header.nritems++; 655 lower->header.nritems++;
653 if (lower->keys[1].objectid == 0) 656 if (lower->keys[1].objectid == 0)
654 BUG(); 657 BUG();
655 write_tree_block(root, path->nodes[level]); 658 dirty_tree_block(root, path->nodes[level]);
656 return 0; 659 return 0;
657} 660}
658 661
@@ -698,10 +701,10 @@ static int split_node(struct ctree_root *root, struct ctree_path *path,
698 c->header.nritems = mid; 701 c->header.nritems = mid;
699 ret = 0; 702 ret = 0;
700 703
701 wret = write_tree_block(root, t); 704 wret = dirty_tree_block(root, t);
702 if (wret) 705 if (wret)
703 ret = wret; 706 ret = wret;
704 wret = write_tree_block(root, split_buffer); 707 wret = dirty_tree_block(root, split_buffer);
705 if (wret) 708 if (wret)
706 ret = wret; 709 ret = wret;
707 wret = insert_ptr(root, path, split->keys, split_buffer->blocknr, 710 wret = insert_ptr(root, path, split->keys, split_buffer->blocknr,
@@ -815,11 +818,11 @@ static int push_leaf_right(struct ctree_root *root, struct ctree_path *path,
815 } 818 }
816 left->header.nritems -= push_items; 819 left->header.nritems -= push_items;
817 820
818 write_tree_block(root, left_buf); 821 dirty_tree_block(root, left_buf);
819 write_tree_block(root, right_buf); 822 dirty_tree_block(root, right_buf);
820 memcpy(upper->node.keys + slot + 1, 823 memcpy(upper->node.keys + slot + 1,
821 &right->items[0].key, sizeof(struct key)); 824 &right->items[0].key, sizeof(struct key));
822 write_tree_block(root, upper); 825 dirty_tree_block(root, upper);
823 /* then fixup the leaf pointer in the path */ 826 /* then fixup the leaf pointer in the path */
824 if (path->slots[0] >= left->header.nritems) { 827 if (path->slots[0] >= left->header.nritems) {
825 path->slots[0] -= left->header.nritems; 828 path->slots[0] -= left->header.nritems;
@@ -909,10 +912,10 @@ static int push_leaf_left(struct ctree_root *root, struct ctree_path *path,
909 push_space = right->items[i].offset; 912 push_space = right->items[i].offset;
910 } 913 }
911 914
912 wret = write_tree_block(root, t); 915 wret = dirty_tree_block(root, t);
913 if (wret) 916 if (wret)
914 ret = wret; 917 ret = wret;
915 wret = write_tree_block(root, right_buf); 918 wret = dirty_tree_block(root, right_buf);
916 if (wret) 919 if (wret)
917 ret = wret; 920 ret = wret;
918 921
@@ -1019,10 +1022,10 @@ static int split_leaf(struct ctree_root *root, struct ctree_path *path,
1019 right_buffer->blocknr, path->slots[1] + 1, 1); 1022 right_buffer->blocknr, path->slots[1] + 1, 1);
1020 if (wret) 1023 if (wret)
1021 ret = wret; 1024 ret = wret;
1022 wret = write_tree_block(root, right_buffer); 1025 wret = dirty_tree_block(root, right_buffer);
1023 if (wret) 1026 if (wret)
1024 ret = wret; 1027 ret = wret;
1025 wret = write_tree_block(root, l_buf); 1028 wret = dirty_tree_block(root, l_buf);
1026 if (wret) 1029 if (wret)
1027 ret = wret; 1030 ret = wret;
1028 1031
@@ -1062,12 +1065,14 @@ int insert_item(struct ctree_root *root, struct key *key,
1062 ret = search_slot(root, key, &path, data_size); 1065 ret = search_slot(root, key, &path, data_size);
1063 if (ret == 0) { 1066 if (ret == 0) {
1064 release_path(root, &path); 1067 release_path(root, &path);
1065 return -EEXIST; 1068 ret = -EEXIST;
1066 } 1069 wret = commit_transaction(root);
1067 if (ret < 0) { 1070 if (wret)
1068 release_path(root, &path); 1071 ret = wret;
1069 return ret; 1072 return ret;
1070 } 1073 }
1074 if (ret < 0)
1075 goto out;
1071 1076
1072 slot_orig = path.slots[0]; 1077 slot_orig = path.slots[0];
1073 leaf_buf = path.nodes[0]; 1078 leaf_buf = path.nodes[0];
@@ -1113,14 +1118,18 @@ int insert_item(struct ctree_root *root, struct key *key,
1113 if (slot == 0) 1118 if (slot == 0)
1114 ret = fixup_low_keys(root, &path, key, 1); 1119 ret = fixup_low_keys(root, &path, key, 1);
1115 1120
1116 wret = write_tree_block(root, leaf_buf); 1121 wret = dirty_tree_block(root, leaf_buf);
1117 if (wret) 1122 if (wret)
1118 ret = wret; 1123 ret = wret;
1119 1124
1120 if (leaf_free_space(leaf) < 0) 1125 if (leaf_free_space(leaf) < 0)
1121 BUG(); 1126 BUG();
1122 check_leaf(&path, 0); 1127 check_leaf(&path, 0);
1128out:
1123 release_path(root, &path); 1129 release_path(root, &path);
1130 wret = commit_transaction(root);
1131 if (wret)
1132 ret = wret;
1124 return ret; 1133 return ret;
1125} 1134}
1126 1135
@@ -1160,7 +1169,7 @@ static int del_ptr(struct ctree_root *root, struct ctree_path *path, int level,
1160 if (wret) 1169 if (wret)
1161 ret = wret; 1170 ret = wret;
1162 } 1171 }
1163 wret = write_tree_block(root, parent); 1172 wret = dirty_tree_block(root, parent);
1164 if (wret) 1173 if (wret)
1165 ret = wret; 1174 ret = wret;
1166 return ret; 1175 return ret;
@@ -1203,8 +1212,9 @@ int del_item(struct ctree_root *root, struct ctree_path *path)
1203 if (leaf->header.nritems == 0) { 1212 if (leaf->header.nritems == 0) {
1204 if (leaf_buf == root->node) { 1213 if (leaf_buf == root->node) {
1205 leaf->header.flags = node_level(0); 1214 leaf->header.flags = node_level(0);
1206 write_tree_block(root, leaf_buf); 1215 dirty_tree_block(root, leaf_buf);
1207 } else { 1216 } else {
1217 clean_tree_block(root, leaf_buf);
1208 wret = del_ptr(root, path, 1, path->slots[1]); 1218 wret = del_ptr(root, path, 1, path->slots[1]);
1209 if (wret) 1219 if (wret)
1210 ret = wret; 1220 ret = wret;
@@ -1220,7 +1230,7 @@ int del_item(struct ctree_root *root, struct ctree_path *path)
1220 if (wret) 1230 if (wret)
1221 ret = wret; 1231 ret = wret;
1222 } 1232 }
1223 wret = write_tree_block(root, leaf_buf); 1233 wret = dirty_tree_block(root, leaf_buf);
1224 if (wret) 1234 if (wret)
1225 ret = wret; 1235 ret = wret;
1226 1236
@@ -1242,6 +1252,7 @@ int del_item(struct ctree_root *root, struct ctree_path *path)
1242 } 1252 }
1243 if (leaf->header.nritems == 0) { 1253 if (leaf->header.nritems == 0) {
1244 u64 blocknr = leaf_buf->blocknr; 1254 u64 blocknr = leaf_buf->blocknr;
1255 clean_tree_block(root, leaf_buf);
1245 wret = del_ptr(root, path, 1, slot); 1256 wret = del_ptr(root, path, 1, slot);
1246 if (wret) 1257 if (wret)
1247 ret = wret; 1258 ret = wret;
@@ -1254,6 +1265,9 @@ int del_item(struct ctree_root *root, struct ctree_path *path)
1254 } 1265 }
1255 } 1266 }
1256 } 1267 }
1268 wret = commit_transaction(root);
1269 if (wret)
1270 ret = wret;
1257 return ret; 1271 return ret;
1258} 1272}
1259 1273
diff --git a/fs/btrfs/ctree.h b/fs/btrfs/ctree.h
index 18daccd84535..6b4dabd47698 100644
--- a/fs/btrfs/ctree.h
+++ b/fs/btrfs/ctree.h
@@ -1,6 +1,8 @@
1#ifndef __CTREE__ 1#ifndef __CTREE__
2#define __CTREE__ 2#define __CTREE__
3 3
4#include "list.h"
5
4#define CTREE_BLOCKSIZE 1024 6#define CTREE_BLOCKSIZE 1024
5 7
6/* 8/*
@@ -53,6 +55,9 @@ struct ctree_root {
53 struct key current_insert; 55 struct key current_insert;
54 int fp; 56 int fp;
55 struct radix_tree_root cache_radix; 57 struct radix_tree_root cache_radix;
58 struct list_head trans;
59 struct list_head cache;
60 int cache_size;
56}; 61};
57 62
58/* 63/*
diff --git a/fs/btrfs/disk-io.c b/fs/btrfs/disk-io.c
index c42dc72706bf..656ace6147a8 100644
--- a/fs/btrfs/disk-io.c
+++ b/fs/btrfs/disk-io.c
@@ -11,6 +11,8 @@
11#include "disk-io.h" 11#include "disk-io.h"
12 12
13static int allocated_blocks = 0; 13static int allocated_blocks = 0;
14int cache_size = 0;
15int cache_max = 10000;
14 16
15static int check_tree_block(struct ctree_root *root, struct tree_buffer *buf) 17static int check_tree_block(struct ctree_root *root, struct tree_buffer *buf)
16{ 18{
@@ -21,6 +23,25 @@ static int check_tree_block(struct ctree_root *root, struct tree_buffer *buf)
21 return 0; 23 return 0;
22} 24}
23 25
26static int free_some_buffers(struct ctree_root *root)
27{
28 struct list_head *node, *next;
29 struct tree_buffer *b;
30 if (root->cache_size < cache_max)
31 return 0;
32 list_for_each_safe(node, next, &root->cache) {
33 b = list_entry(node, struct tree_buffer, cache);
34 if (b->count == 1) {
35 BUG_ON(!list_empty(&b->dirty));
36 list_del_init(&b->cache);
37 tree_block_release(root, b);
38 if (root->cache_size < cache_max)
39 return 0;
40 }
41 }
42 return 0;
43}
44
24struct tree_buffer *alloc_tree_block(struct ctree_root *root, u64 blocknr) 45struct tree_buffer *alloc_tree_block(struct ctree_root *root, u64 blocknr)
25{ 46{
26 struct tree_buffer *buf; 47 struct tree_buffer *buf;
@@ -30,10 +51,14 @@ struct tree_buffer *alloc_tree_block(struct ctree_root *root, u64 blocknr)
30 return buf; 51 return buf;
31 allocated_blocks++; 52 allocated_blocks++;
32 buf->blocknr = blocknr; 53 buf->blocknr = blocknr;
33 buf->count = 1; 54 buf->count = 2;
55 INIT_LIST_HEAD(&buf->dirty);
56 free_some_buffers(root);
34 radix_tree_preload(GFP_KERNEL); 57 radix_tree_preload(GFP_KERNEL);
35 ret = radix_tree_insert(&root->cache_radix, blocknr, buf); 58 ret = radix_tree_insert(&root->cache_radix, blocknr, buf);
36 radix_tree_preload_end(); 59 radix_tree_preload_end();
60 list_add_tail(&buf->cache, &root->cache);
61 root->cache_size++;
37 if (ret) { 62 if (ret) {
38 free(buf); 63 free(buf);
39 return NULL; 64 return NULL;
@@ -57,7 +82,6 @@ struct tree_buffer *find_tree_block(struct ctree_root *root, u64 blocknr)
57 return buf; 82 return buf;
58} 83}
59 84
60
61struct tree_buffer *read_tree_block(struct ctree_root *root, u64 blocknr) 85struct tree_buffer *read_tree_block(struct ctree_root *root, u64 blocknr)
62{ 86{
63 loff_t offset = blocknr * CTREE_BLOCKSIZE; 87 loff_t offset = blocknr * CTREE_BLOCKSIZE;
@@ -82,6 +106,24 @@ struct tree_buffer *read_tree_block(struct ctree_root *root, u64 blocknr)
82 return buf; 106 return buf;
83} 107}
84 108
109int dirty_tree_block(struct ctree_root *root, struct tree_buffer *buf)
110{
111 if (!list_empty(&buf->dirty))
112 return 0;
113 list_add_tail(&buf->dirty, &root->trans);
114 buf->count++;
115 return 0;
116}
117
118int clean_tree_block(struct ctree_root *root, struct tree_buffer *buf)
119{
120 if (!list_empty(&buf->dirty)) {
121 list_del_init(&buf->dirty);
122 tree_block_release(root, buf);
123 }
124 return 0;
125}
126
85int write_tree_block(struct ctree_root *root, struct tree_buffer *buf) 127int write_tree_block(struct ctree_root *root, struct tree_buffer *buf)
86{ 128{
87 u64 blocknr = buf->blocknr; 129 u64 blocknr = buf->blocknr;
@@ -96,9 +138,37 @@ int write_tree_block(struct ctree_root *root, struct tree_buffer *buf)
96 return 0; 138 return 0;
97} 139}
98 140
141static int __commit_transaction(struct ctree_root *root)
142{
143 struct tree_buffer *b;
144 int ret = 0;
145 int wret;
146 while(!list_empty(&root->trans)) {
147 b = list_entry(root->trans.next, struct tree_buffer, dirty);
148 list_del_init(&b->dirty);
149 wret = write_tree_block(root, b);
150 if (wret)
151 ret = wret;
152 tree_block_release(root, b);
153 }
154 return ret;
155}
156
157int commit_transaction(struct ctree_root *root)
158{
159 int ret;
160 ret = __commit_transaction(root);
161 if (!ret && root != root->extent_root)
162 ret = __commit_transaction(root->extent_root);
163 BUG_ON(ret);
164 return ret;
165}
166
99static int __setup_root(struct ctree_root *root, struct ctree_root *extent_root, 167static int __setup_root(struct ctree_root *root, struct ctree_root *extent_root,
100 struct ctree_root_info *info, int fp) 168 struct ctree_root_info *info, int fp)
101{ 169{
170 INIT_LIST_HEAD(&root->trans);
171 INIT_LIST_HEAD(&root->cache);
102 root->fp = fp; 172 root->fp = fp;
103 root->node = NULL; 173 root->node = NULL;
104 root->node = read_tree_block(root, info->tree_root); 174 root->node = read_tree_block(root, info->tree_root);
@@ -157,8 +227,23 @@ int write_ctree_super(struct ctree_root *root, struct ctree_super_block *s)
157 return 0; 227 return 0;
158} 228}
159 229
230static int drop_cache(struct ctree_root *root)
231{
232 while(!list_empty(&root->cache)) {
233 struct tree_buffer *b = list_entry(root->cache.next,
234 struct tree_buffer, cache);
235 list_del_init(&b->cache);
236 tree_block_release(root, b);
237 }
238 return 0;
239}
160int close_ctree(struct ctree_root *root) 240int close_ctree(struct ctree_root *root)
161{ 241{
242 drop_cache(root->extent_root);
243 drop_cache(root);
244 BUG_ON(!list_empty(&root->trans));
245 BUG_ON(!list_empty(&root->extent_root->trans));
246
162 close(root->fp); 247 close(root->fp);
163 if (root->node) 248 if (root->node)
164 tree_block_release(root, root->node); 249 tree_block_release(root, root->node);
@@ -182,6 +267,8 @@ void tree_block_release(struct ctree_root *root, struct tree_buffer *buf)
182 free(buf); 267 free(buf);
183 BUG_ON(allocated_blocks == 0); 268 BUG_ON(allocated_blocks == 0);
184 allocated_blocks--; 269 allocated_blocks--;
270 BUG_ON(root->cache_size == 0);
271 root->cache_size--;
185 } 272 }
186} 273}
187 274
diff --git a/fs/btrfs/disk-io.h b/fs/btrfs/disk-io.h
index 2729b757ddc1..b5dee2fae4da 100644
--- a/fs/btrfs/disk-io.h
+++ b/fs/btrfs/disk-io.h
@@ -1,5 +1,6 @@
1#ifndef __DISKIO__ 1#ifndef __DISKIO__
2#define __DISKIO__ 2#define __DISKIO__
3#include "list.h"
3 4
4struct tree_buffer { 5struct tree_buffer {
5 u64 blocknr; 6 u64 blocknr;
@@ -8,11 +9,16 @@ struct tree_buffer {
8 struct node node; 9 struct node node;
9 struct leaf leaf; 10 struct leaf leaf;
10 }; 11 };
12 struct list_head dirty;
13 struct list_head cache;
11}; 14};
12 15
13struct tree_buffer *read_tree_block(struct ctree_root *root, u64 blocknr); 16struct tree_buffer *read_tree_block(struct ctree_root *root, u64 blocknr);
14struct tree_buffer *find_tree_block(struct ctree_root *root, u64 blocknr); 17struct tree_buffer *find_tree_block(struct ctree_root *root, u64 blocknr);
15int write_tree_block(struct ctree_root *root, struct tree_buffer *buf); 18int write_tree_block(struct ctree_root *root, struct tree_buffer *buf);
19int dirty_tree_block(struct ctree_root *root, struct tree_buffer *buf);
20int clean_tree_block(struct ctree_root *root, struct tree_buffer *buf);
21int commit_transaction(struct ctree_root *root);
16struct ctree_root *open_ctree(char *filename, struct ctree_super_block *s); 22struct ctree_root *open_ctree(char *filename, struct ctree_super_block *s);
17int close_ctree(struct ctree_root *root); 23int close_ctree(struct ctree_root *root);
18void tree_block_release(struct ctree_root *root, struct tree_buffer *buf); 24void tree_block_release(struct ctree_root *root, struct tree_buffer *buf);
diff --git a/fs/btrfs/list.h b/fs/btrfs/list.h
new file mode 100644
index 000000000000..1aafafb13370
--- /dev/null
+++ b/fs/btrfs/list.h
@@ -0,0 +1,418 @@
1#ifndef _LINUX_LIST_H
2#define _LINUX_LIST_H
3
4#define LIST_POISON1 ((void *) 0x00100100)
5#define LIST_POISON2 ((void *) 0x00200200)
6
7/*
8 * Simple doubly linked list implementation.
9 *
10 * Some of the internal functions ("__xxx") are useful when
11 * manipulating whole lists rather than single entries, as
12 * sometimes we already know the next/prev entries and we can
13 * generate better code by using them directly rather than
14 * using the generic single-entry routines.
15 */
16
17struct list_head {
18 struct list_head *next, *prev;
19};
20
21#define LIST_HEAD_INIT(name) { &(name), &(name) }
22
23#define LIST_HEAD(name) \
24 struct list_head name = LIST_HEAD_INIT(name)
25
26static inline void INIT_LIST_HEAD(struct list_head *list)
27{
28 list->next = list;
29 list->prev = list;
30}
31
32/*
33 * Insert a new entry between two known consecutive entries.
34 *
35 * This is only for internal list manipulation where we know
36 * the prev/next entries already!
37 */
38#ifndef CONFIG_DEBUG_LIST
39static inline void __list_add(struct list_head *new,
40 struct list_head *prev,
41 struct list_head *next)
42{
43 next->prev = new;
44 new->next = next;
45 new->prev = prev;
46 prev->next = new;
47}
48#else
49extern void __list_add(struct list_head *new,
50 struct list_head *prev,
51 struct list_head *next);
52#endif
53
54/**
55 * list_add - add a new entry
56 * @new: new entry to be added
57 * @head: list head to add it after
58 *
59 * Insert a new entry after the specified head.
60 * This is good for implementing stacks.
61 */
62#ifndef CONFIG_DEBUG_LIST
63static inline void list_add(struct list_head *new, struct list_head *head)
64{
65 __list_add(new, head, head->next);
66}
67#else
68extern void list_add(struct list_head *new, struct list_head *head);
69#endif
70
71
72/**
73 * list_add_tail - add a new entry
74 * @new: new entry to be added
75 * @head: list head to add it before
76 *
77 * Insert a new entry before the specified head.
78 * This is useful for implementing queues.
79 */
80static inline void list_add_tail(struct list_head *new, struct list_head *head)
81{
82 __list_add(new, head->prev, head);
83}
84
85/*
86 * Delete a list entry by making the prev/next entries
87 * point to each other.
88 *
89 * This is only for internal list manipulation where we know
90 * the prev/next entries already!
91 */
92static inline void __list_del(struct list_head * prev, struct list_head * next)
93{
94 next->prev = prev;
95 prev->next = next;
96}
97
98/**
99 * list_del - deletes entry from list.
100 * @entry: the element to delete from the list.
101 * Note: list_empty on entry does not return true after this, the entry is
102 * in an undefined state.
103 */
104#ifndef CONFIG_DEBUG_LIST
105static inline void list_del(struct list_head *entry)
106{
107 __list_del(entry->prev, entry->next);
108 entry->next = LIST_POISON1;
109 entry->prev = LIST_POISON2;
110}
111#else
112extern void list_del(struct list_head *entry);
113#endif
114
115/**
116 * list_replace - replace old entry by new one
117 * @old : the element to be replaced
118 * @new : the new element to insert
119 * Note: if 'old' was empty, it will be overwritten.
120 */
121static inline void list_replace(struct list_head *old,
122 struct list_head *new)
123{
124 new->next = old->next;
125 new->next->prev = new;
126 new->prev = old->prev;
127 new->prev->next = new;
128}
129
130static inline void list_replace_init(struct list_head *old,
131 struct list_head *new)
132{
133 list_replace(old, new);
134 INIT_LIST_HEAD(old);
135}
136/**
137 * list_del_init - deletes entry from list and reinitialize it.
138 * @entry: the element to delete from the list.
139 */
140static inline void list_del_init(struct list_head *entry)
141{
142 __list_del(entry->prev, entry->next);
143 INIT_LIST_HEAD(entry);
144}
145
146/**
147 * list_move - delete from one list and add as another's head
148 * @list: the entry to move
149 * @head: the head that will precede our entry
150 */
151static inline void list_move(struct list_head *list, struct list_head *head)
152{
153 __list_del(list->prev, list->next);
154 list_add(list, head);
155}
156
157/**
158 * list_move_tail - delete from one list and add as another's tail
159 * @list: the entry to move
160 * @head: the head that will follow our entry
161 */
162static inline void list_move_tail(struct list_head *list,
163 struct list_head *head)
164{
165 __list_del(list->prev, list->next);
166 list_add_tail(list, head);
167}
168
169/**
170 * list_is_last - tests whether @list is the last entry in list @head
171 * @list: the entry to test
172 * @head: the head of the list
173 */
174static inline int list_is_last(const struct list_head *list,
175 const struct list_head *head)
176{
177 return list->next == head;
178}
179
180/**
181 * list_empty - tests whether a list is empty
182 * @head: the list to test.
183 */
184static inline int list_empty(const struct list_head *head)
185{
186 return head->next == head;
187}
188
189/**
190 * list_empty_careful - tests whether a list is empty and not being modified
191 * @head: the list to test
192 *
193 * Description:
194 * tests whether a list is empty _and_ checks that no other CPU might be
195 * in the process of modifying either member (next or prev)
196 *
197 * NOTE: using list_empty_careful() without synchronization
198 * can only be safe if the only activity that can happen
199 * to the list entry is list_del_init(). Eg. it cannot be used
200 * if another CPU could re-list_add() it.
201 */
202static inline int list_empty_careful(const struct list_head *head)
203{
204 struct list_head *next = head->next;
205 return (next == head) && (next == head->prev);
206}
207
208static inline void __list_splice(struct list_head *list,
209 struct list_head *head)
210{
211 struct list_head *first = list->next;
212 struct list_head *last = list->prev;
213 struct list_head *at = head->next;
214
215 first->prev = head;
216 head->next = first;
217
218 last->next = at;
219 at->prev = last;
220}
221
222/**
223 * list_splice - join two lists
224 * @list: the new list to add.
225 * @head: the place to add it in the first list.
226 */
227static inline void list_splice(struct list_head *list, struct list_head *head)
228{
229 if (!list_empty(list))
230 __list_splice(list, head);
231}
232
233/**
234 * list_splice_init - join two lists and reinitialise the emptied list.
235 * @list: the new list to add.
236 * @head: the place to add it in the first list.
237 *
238 * The list at @list is reinitialised
239 */
240static inline void list_splice_init(struct list_head *list,
241 struct list_head *head)
242{
243 if (!list_empty(list)) {
244 __list_splice(list, head);
245 INIT_LIST_HEAD(list);
246 }
247}
248
249/**
250 * list_entry - get the struct for this entry
251 * @ptr: the &struct list_head pointer.
252 * @type: the type of the struct this is embedded in.
253 * @member: the name of the list_struct within the struct.
254 */
255#define list_entry(ptr, type, member) \
256 container_of(ptr, type, member)
257
258/**
259 * list_for_each - iterate over a list
260 * @pos: the &struct list_head to use as a loop cursor.
261 * @head: the head for your list.
262 */
263#define list_for_each(pos, head) \
264 for (pos = (head)->next; prefetch(pos->next), pos != (head); \
265 pos = pos->next)
266
267/**
268 * __list_for_each - iterate over a list
269 * @pos: the &struct list_head to use as a loop cursor.
270 * @head: the head for your list.
271 *
272 * This variant differs from list_for_each() in that it's the
273 * simplest possible list iteration code, no prefetching is done.
274 * Use this for code that knows the list to be very short (empty
275 * or 1 entry) most of the time.
276 */
277#define __list_for_each(pos, head) \
278 for (pos = (head)->next; pos != (head); pos = pos->next)
279
280/**
281 * list_for_each_prev - iterate over a list backwards
282 * @pos: the &struct list_head to use as a loop cursor.
283 * @head: the head for your list.
284 */
285#define list_for_each_prev(pos, head) \
286 for (pos = (head)->prev; prefetch(pos->prev), pos != (head); \
287 pos = pos->prev)
288
289/**
290 * list_for_each_safe - iterate over a list safe against removal of list entry
291 * @pos: the &struct list_head to use as a loop cursor.
292 * @n: another &struct list_head to use as temporary storage
293 * @head: the head for your list.
294 */
295#define list_for_each_safe(pos, n, head) \
296 for (pos = (head)->next, n = pos->next; pos != (head); \
297 pos = n, n = pos->next)
298
299/**
300 * list_for_each_entry - iterate over list of given type
301 * @pos: the type * to use as a loop cursor.
302 * @head: the head for your list.
303 * @member: the name of the list_struct within the struct.
304 */
305#define list_for_each_entry(pos, head, member) \
306 for (pos = list_entry((head)->next, typeof(*pos), member); \
307 prefetch(pos->member.next), &pos->member != (head); \
308 pos = list_entry(pos->member.next, typeof(*pos), member))
309
310/**
311 * list_for_each_entry_reverse - iterate backwards over list of given type.
312 * @pos: the type * to use as a loop cursor.
313 * @head: the head for your list.
314 * @member: the name of the list_struct within the struct.
315 */
316#define list_for_each_entry_reverse(pos, head, member) \
317 for (pos = list_entry((head)->prev, typeof(*pos), member); \
318 prefetch(pos->member.prev), &pos->member != (head); \
319 pos = list_entry(pos->member.prev, typeof(*pos), member))
320
321/**
322 * list_prepare_entry - prepare a pos entry for use in list_for_each_entry_continue
323 * @pos: the type * to use as a start point
324 * @head: the head of the list
325 * @member: the name of the list_struct within the struct.
326 *
327 * Prepares a pos entry for use as a start point in list_for_each_entry_continue.
328 */
329#define list_prepare_entry(pos, head, member) \
330 ((pos) ? : list_entry(head, typeof(*pos), member))
331
332/**
333 * list_for_each_entry_continue - continue iteration over list of given type
334 * @pos: the type * to use as a loop cursor.
335 * @head: the head for your list.
336 * @member: the name of the list_struct within the struct.
337 *
338 * Continue to iterate over list of given type, continuing after
339 * the current position.
340 */
341#define list_for_each_entry_continue(pos, head, member) \
342 for (pos = list_entry(pos->member.next, typeof(*pos), member); \
343 prefetch(pos->member.next), &pos->member != (head); \
344 pos = list_entry(pos->member.next, typeof(*pos), member))
345
346/**
347 * list_for_each_entry_from - iterate over list of given type from the current point
348 * @pos: the type * to use as a loop cursor.
349 * @head: the head for your list.
350 * @member: the name of the list_struct within the struct.
351 *
352 * Iterate over list of given type, continuing from current position.
353 */
354#define list_for_each_entry_from(pos, head, member) \
355 for (; prefetch(pos->member.next), &pos->member != (head); \
356 pos = list_entry(pos->member.next, typeof(*pos), member))
357
358/**
359 * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry
360 * @pos: the type * to use as a loop cursor.
361 * @n: another type * to use as temporary storage
362 * @head: the head for your list.
363 * @member: the name of the list_struct within the struct.
364 */
365#define list_for_each_entry_safe(pos, n, head, member) \
366 for (pos = list_entry((head)->next, typeof(*pos), member), \
367 n = list_entry(pos->member.next, typeof(*pos), member); \
368 &pos->member != (head); \
369 pos = n, n = list_entry(n->member.next, typeof(*n), member))
370
371/**
372 * list_for_each_entry_safe_continue
373 * @pos: the type * to use as a loop cursor.
374 * @n: another type * to use as temporary storage
375 * @head: the head for your list.
376 * @member: the name of the list_struct within the struct.
377 *
378 * Iterate over list of given type, continuing after current point,
379 * safe against removal of list entry.
380 */
381#define list_for_each_entry_safe_continue(pos, n, head, member) \
382 for (pos = list_entry(pos->member.next, typeof(*pos), member), \
383 n = list_entry(pos->member.next, typeof(*pos), member); \
384 &pos->member != (head); \
385 pos = n, n = list_entry(n->member.next, typeof(*n), member))
386
387/**
388 * list_for_each_entry_safe_from
389 * @pos: the type * to use as a loop cursor.
390 * @n: another type * to use as temporary storage
391 * @head: the head for your list.
392 * @member: the name of the list_struct within the struct.
393 *
394 * Iterate over list of given type from current point, safe against
395 * removal of list entry.
396 */
397#define list_for_each_entry_safe_from(pos, n, head, member) \
398 for (n = list_entry(pos->member.next, typeof(*pos), member); \
399 &pos->member != (head); \
400 pos = n, n = list_entry(n->member.next, typeof(*n), member))
401
402/**
403 * list_for_each_entry_safe_reverse
404 * @pos: the type * to use as a loop cursor.
405 * @n: another type * to use as temporary storage
406 * @head: the head for your list.
407 * @member: the name of the list_struct within the struct.
408 *
409 * Iterate backwards over list of given type, safe against removal
410 * of list entry.
411 */
412#define list_for_each_entry_safe_reverse(pos, n, head, member) \
413 for (pos = list_entry((head)->prev, typeof(*pos), member), \
414 n = list_entry(pos->member.prev, typeof(*pos), member); \
415 &pos->member != (head); \
416 pos = n, n = list_entry(n->member.prev, typeof(*n), member))
417
418#endif
generated by cgit v1.2.2 (git 2.25.0) at 2024-12-12 21:03:36 -0500