Searched refs:tree (Results 1 - 200 of 2153) sorted by relevance

1234567891011

/linux-4.1.27/fs/hfs/
H A Dbtree.c20 struct hfs_btree *tree; hfs_btree_open() local
26 tree = kzalloc(sizeof(*tree), GFP_KERNEL); hfs_btree_open()
27 if (!tree) hfs_btree_open()
30 mutex_init(&tree->tree_lock); hfs_btree_open()
31 spin_lock_init(&tree->hash_lock); hfs_btree_open()
33 tree->sb = sb; hfs_btree_open()
34 tree->cnid = id; hfs_btree_open()
35 tree->keycmp = keycmp; hfs_btree_open()
37 tree->inode = iget_locked(sb, id); hfs_btree_open()
38 if (!tree->inode) hfs_btree_open()
40 BUG_ON(!(tree->inode->i_state & I_NEW)); hfs_btree_open()
43 HFS_I(tree->inode)->flags = 0; hfs_btree_open()
44 mutex_init(&HFS_I(tree->inode)->extents_lock); hfs_btree_open()
47 hfs_inode_read_fork(tree->inode, mdb->drXTExtRec, mdb->drXTFlSize, hfs_btree_open()
49 if (HFS_I(tree->inode)->alloc_blocks > hfs_btree_open()
50 HFS_I(tree->inode)->first_blocks) { hfs_btree_open()
52 unlock_new_inode(tree->inode); hfs_btree_open()
56 tree->inode->i_mapping->a_ops = &hfs_btree_aops; hfs_btree_open()
59 hfs_inode_read_fork(tree->inode, mdb->drCTExtRec, mdb->drCTFlSize, hfs_btree_open()
62 if (!HFS_I(tree->inode)->first_blocks) { hfs_btree_open()
64 unlock_new_inode(tree->inode); hfs_btree_open()
68 tree->inode->i_mapping->a_ops = &hfs_btree_aops; hfs_btree_open()
74 unlock_new_inode(tree->inode); hfs_btree_open()
76 mapping = tree->inode->i_mapping; hfs_btree_open()
83 tree->root = be32_to_cpu(head->root); hfs_btree_open()
84 tree->leaf_count = be32_to_cpu(head->leaf_count); hfs_btree_open()
85 tree->leaf_head = be32_to_cpu(head->leaf_head); hfs_btree_open()
86 tree->leaf_tail = be32_to_cpu(head->leaf_tail); hfs_btree_open()
87 tree->node_count = be32_to_cpu(head->node_count); hfs_btree_open()
88 tree->free_nodes = be32_to_cpu(head->free_nodes); hfs_btree_open()
89 tree->attributes = be32_to_cpu(head->attributes); hfs_btree_open()
90 tree->node_size = be16_to_cpu(head->node_size); hfs_btree_open()
91 tree->max_key_len = be16_to_cpu(head->max_key_len); hfs_btree_open()
92 tree->depth = be16_to_cpu(head->depth); hfs_btree_open()
94 size = tree->node_size; hfs_btree_open()
97 if (!tree->node_count) hfs_btree_open()
101 if (tree->max_key_len != HFS_MAX_EXT_KEYLEN) { hfs_btree_open()
103 tree->max_key_len); hfs_btree_open()
108 if (tree->max_key_len != HFS_MAX_CAT_KEYLEN) { hfs_btree_open()
110 tree->max_key_len); hfs_btree_open()
118 tree->node_size_shift = ffs(size) - 1; hfs_btree_open()
119 tree->pages_per_bnode = (tree->node_size + PAGE_CACHE_SIZE - 1) >> PAGE_CACHE_SHIFT; hfs_btree_open()
123 return tree; hfs_btree_open()
128 tree->inode->i_mapping->a_ops = &hfs_aops; hfs_btree_open()
129 iput(tree->inode); hfs_btree_open()
131 kfree(tree); hfs_btree_open()
136 void hfs_btree_close(struct hfs_btree *tree) hfs_btree_close() argument
141 if (!tree) hfs_btree_close()
145 while ((node = tree->node_hash[i])) { hfs_btree_close()
146 tree->node_hash[i] = node->next_hash; hfs_btree_close()
149 node->tree->cnid, node->this, hfs_btree_close()
152 tree->node_hash_cnt--; hfs_btree_close()
155 iput(tree->inode); hfs_btree_close()
156 kfree(tree); hfs_btree_close()
159 void hfs_btree_write(struct hfs_btree *tree) hfs_btree_write() argument
165 node = hfs_bnode_find(tree, 0); hfs_btree_write()
173 head->root = cpu_to_be32(tree->root); hfs_btree_write()
174 head->leaf_count = cpu_to_be32(tree->leaf_count); hfs_btree_write()
175 head->leaf_head = cpu_to_be32(tree->leaf_head); hfs_btree_write()
176 head->leaf_tail = cpu_to_be32(tree->leaf_tail); hfs_btree_write()
177 head->node_count = cpu_to_be32(tree->node_count); hfs_btree_write()
178 head->free_nodes = cpu_to_be32(tree->free_nodes); hfs_btree_write()
179 head->attributes = cpu_to_be32(tree->attributes); hfs_btree_write()
180 head->depth = cpu_to_be16(tree->depth); hfs_btree_write()
189 struct hfs_btree *tree = prev->tree; hfs_bmap_new_bmap() local
194 node = hfs_bnode_create(tree, idx); hfs_bmap_new_bmap()
198 if (!tree->free_nodes) hfs_bmap_new_bmap()
200 tree->free_nodes--; hfs_bmap_new_bmap()
207 hfs_bnode_clear(node, 0, tree->node_size); hfs_bmap_new_bmap()
216 hfs_bnode_write_u16(node, tree->node_size - 2, 14); hfs_bmap_new_bmap()
217 hfs_bnode_write_u16(node, tree->node_size - 4, tree->node_size - 6); hfs_bmap_new_bmap()
222 struct hfs_bnode *hfs_bmap_alloc(struct hfs_btree *tree) hfs_bmap_alloc() argument
233 while (!tree->free_nodes) { hfs_bmap_alloc()
234 struct inode *inode = tree->inode; hfs_bmap_alloc()
243 HFS_SB(tree->sb)->alloc_blksz; hfs_bmap_alloc()
245 tree->sb->s_blocksize_bits; hfs_bmap_alloc()
247 count = inode->i_size >> tree->node_size_shift; hfs_bmap_alloc()
248 tree->free_nodes = count - tree->node_count; hfs_bmap_alloc()
249 tree->node_count = count; hfs_bmap_alloc()
253 node = hfs_bnode_find(tree, nidx); hfs_bmap_alloc()
275 tree->free_nodes--; hfs_bmap_alloc()
276 mark_inode_dirty(tree->inode); hfs_bmap_alloc()
278 return hfs_bnode_create(tree, idx); hfs_bmap_alloc()
296 next_node = hfs_bnode_find(tree, nidx); hfs_bmap_alloc()
313 struct hfs_btree *tree; hfs_bmap_free() local
320 tree = node->tree; hfs_bmap_free()
322 node = hfs_bnode_find(tree, 0); hfs_bmap_free()
338 node = hfs_bnode_find(tree, i); hfs_bmap_free()
367 tree->free_nodes++; hfs_bmap_free()
368 mark_inode_dirty(tree->inode); hfs_bmap_free()
H A Dbnode.c47 struct hfs_btree *tree; hfs_bnode_read_key() local
50 tree = node->tree; hfs_bnode_read_key()
52 tree->attributes & HFS_TREE_VARIDXKEYS) hfs_bnode_read_key()
55 key_len = tree->max_key_len + 1; hfs_bnode_read_key()
100 struct hfs_btree *tree; hfs_bnode_copy() local
106 tree = src_node->tree; hfs_bnode_copy()
147 off = node->tree->node_size - 2; hfs_bnode_dump()
154 if (node->tree->attributes & HFS_TREE_VARIDXKEYS) hfs_bnode_dump()
157 tmp = node->tree->max_key_len + 1; hfs_bnode_dump()
174 struct hfs_btree *tree; hfs_bnode_unlink() local
178 tree = node->tree; hfs_bnode_unlink()
180 tmp = hfs_bnode_find(tree, node->prev); hfs_bnode_unlink()
188 tree->leaf_head = node->next; hfs_bnode_unlink()
191 tmp = hfs_bnode_find(tree, node->next); hfs_bnode_unlink()
199 tree->leaf_tail = node->prev; hfs_bnode_unlink()
206 tree->root = 0; hfs_bnode_unlink()
207 tree->depth = 0; hfs_bnode_unlink()
219 struct hfs_bnode *hfs_bnode_findhash(struct hfs_btree *tree, u32 cnid) hfs_bnode_findhash() argument
223 if (cnid >= tree->node_count) { hfs_bnode_findhash()
228 for (node = tree->node_hash[hfs_bnode_hash(cnid)]; hfs_bnode_findhash()
237 static struct hfs_bnode *__hfs_bnode_create(struct hfs_btree *tree, u32 cnid) __hfs_bnode_create() argument
246 if (cnid >= tree->node_count) { __hfs_bnode_create()
251 sb = tree->inode->i_sb; __hfs_bnode_create()
252 size = sizeof(struct hfs_bnode) + tree->pages_per_bnode * __hfs_bnode_create()
257 node->tree = tree; __hfs_bnode_create()
262 node->tree->cnid, node->this); __hfs_bnode_create()
264 spin_lock(&tree->hash_lock); __hfs_bnode_create()
265 node2 = hfs_bnode_findhash(tree, cnid); __hfs_bnode_create()
268 node->next_hash = tree->node_hash[hash]; __hfs_bnode_create()
269 tree->node_hash[hash] = node; __hfs_bnode_create()
270 tree->node_hash_cnt++; __hfs_bnode_create()
272 spin_unlock(&tree->hash_lock); __hfs_bnode_create()
277 spin_unlock(&tree->hash_lock); __hfs_bnode_create()
279 mapping = tree->inode->i_mapping; __hfs_bnode_create()
280 off = (loff_t)cnid * tree->node_size; __hfs_bnode_create()
283 for (i = 0; i < tree->pages_per_bnode; i++) { __hfs_bnode_create()
305 node->tree->cnid, node->this, atomic_read(&node->refcnt)); hfs_bnode_unhash()
306 for (p = &node->tree->node_hash[hfs_bnode_hash(node->this)]; hfs_bnode_unhash()
311 node->tree->node_hash_cnt--; hfs_bnode_unhash()
314 /* Load a particular node out of a tree */ hfs_bnode_find()
315 struct hfs_bnode *hfs_bnode_find(struct hfs_btree *tree, u32 num) hfs_bnode_find() argument
322 spin_lock(&tree->hash_lock); hfs_bnode_find()
323 node = hfs_bnode_findhash(tree, num); hfs_bnode_find()
326 spin_unlock(&tree->hash_lock); hfs_bnode_find()
332 spin_unlock(&tree->hash_lock); hfs_bnode_find()
333 node = __hfs_bnode_create(tree, num); hfs_bnode_find()
360 if (node->height <= 1 || node->height > tree->depth) hfs_bnode_find()
367 rec_off = tree->node_size - 2; hfs_bnode_find()
375 next_off > tree->node_size || hfs_bnode_find()
402 for (i = 0; i < node->tree->pages_per_bnode; i++) hfs_bnode_free()
408 struct hfs_bnode *hfs_bnode_create(struct hfs_btree *tree, u32 num) hfs_bnode_create() argument
414 spin_lock(&tree->hash_lock); hfs_bnode_create()
415 node = hfs_bnode_findhash(tree, num); hfs_bnode_create()
416 spin_unlock(&tree->hash_lock); hfs_bnode_create()
422 node = __hfs_bnode_create(tree, num); hfs_bnode_create()
432 min((int)PAGE_CACHE_SIZE, (int)tree->node_size)); hfs_bnode_create()
435 for (i = 1; i < tree->pages_per_bnode; i++) { hfs_bnode_create()
451 node->tree->cnid, node->this, hfs_bnode_get()
460 struct hfs_btree *tree = node->tree; hfs_bnode_put() local
464 node->tree->cnid, node->this, hfs_bnode_put()
467 if (!atomic_dec_and_lock(&node->refcnt, &tree->hash_lock)) hfs_bnode_put()
469 for (i = 0; i < tree->pages_per_bnode; i++) { hfs_bnode_put()
477 spin_unlock(&tree->hash_lock); hfs_bnode_put()
482 spin_unlock(&tree->hash_lock); hfs_bnode_put()
H A Dbrec.c15 static int hfs_btree_inc_height(struct hfs_btree *tree);
23 dataoff = node->tree->node_size - (rec + 2) * 2; hfs_brec_lenoff()
38 !(node->tree->attributes & HFS_TREE_VARIDXKEYS)) { hfs_brec_keylen()
39 if (node->tree->attributes & HFS_TREE_BIGKEYS) hfs_brec_keylen()
40 retval = node->tree->max_key_len + 2; hfs_brec_keylen()
42 retval = node->tree->max_key_len + 1; hfs_brec_keylen()
44 recoff = hfs_bnode_read_u16(node, node->tree->node_size - (rec + 1) * 2); hfs_brec_keylen()
47 if (node->tree->attributes & HFS_TREE_BIGKEYS) { hfs_brec_keylen()
49 if (retval > node->tree->max_key_len + 2) { hfs_brec_keylen()
55 if (retval > node->tree->max_key_len + 1) { hfs_brec_keylen()
66 struct hfs_btree *tree; hfs_brec_insert() local
73 tree = fd->tree; hfs_brec_insert()
75 if (!tree->root) hfs_brec_insert()
76 hfs_btree_inc_height(tree); hfs_brec_insert()
77 fd->bnode = hfs_bnode_find(tree, tree->leaf_head); hfs_brec_insert()
92 end_rec_off = tree->node_size - (node->num_recs + 1) * 2; hfs_brec_insert()
106 tree->leaf_count++; hfs_brec_insert()
107 mark_inode_dirty(tree->inode); hfs_brec_insert()
115 idx_rec_off = tree->node_size - (rec + 1) * 2; hfs_brec_insert()
146 hfs_btree_inc_height(tree); hfs_brec_insert()
147 new_node->parent = tree->root; hfs_brec_insert()
149 fd->bnode = hfs_bnode_find(tree, new_node->parent); hfs_brec_insert()
163 if (tree->attributes & HFS_TREE_VARIDXKEYS) hfs_brec_insert()
166 fd->search_key->key_len = tree->max_key_len; hfs_brec_insert()
167 key_len = tree->max_key_len + 1; hfs_brec_insert()
177 struct hfs_btree *tree; hfs_brec_remove() local
181 tree = fd->tree; hfs_brec_remove()
184 rec_off = tree->node_size - (fd->record + 2) * 2; hfs_brec_remove()
185 end_off = tree->node_size - (node->num_recs + 1) * 2; hfs_brec_remove()
188 tree->leaf_count--; hfs_brec_remove()
189 mark_inode_dirty(tree->inode); hfs_brec_remove()
198 parent = hfs_bnode_find(tree, node->parent); hfs_brec_remove()
231 struct hfs_btree *tree; hfs_bnode_split() local
237 tree = fd->tree; hfs_bnode_split()
239 new_node = hfs_bmap_alloc(tree); hfs_bnode_split()
252 next_node = hfs_bnode_find(tree, node->next); hfs_bnode_split()
262 size = tree->node_size / 2 - node->num_recs * 2 - 14; hfs_bnode_split()
263 old_rec_off = tree->node_size - 4; hfs_bnode_split()
298 new_rec_off = tree->node_size - 2; hfs_bnode_split()
337 } else if (node->this == tree->leaf_tail) { hfs_bnode_split()
339 tree->leaf_tail = new_node->this; hfs_bnode_split()
340 mark_inode_dirty(tree->inode); hfs_bnode_split()
352 struct hfs_btree *tree; hfs_brec_update_parent() local
358 tree = fd->tree; hfs_brec_update_parent()
365 parent = hfs_bnode_find(tree, node->parent); hfs_brec_update_parent()
375 if (tree->attributes & HFS_TREE_VARIDXKEYS) hfs_brec_update_parent()
378 fd->keylength = newkeylen = tree->max_key_len + 1; hfs_brec_update_parent()
382 rec_off = tree->node_size - (rec + 2) * 2; hfs_brec_update_parent()
383 end_rec_off = tree->node_size - (parent->num_recs + 1) * 2; hfs_brec_update_parent()
398 rec_off = tree->node_size - (rec + 2) * 2; hfs_brec_update_parent()
399 end_rec_off = tree->node_size - (parent->num_recs + 1) * 2; hfs_brec_update_parent()
416 if (!(tree->attributes & HFS_TREE_VARIDXKEYS)) hfs_brec_update_parent()
426 fd->bnode = hfs_bnode_find(tree, new_node->parent); hfs_brec_update_parent()
451 static int hfs_btree_inc_height(struct hfs_btree *tree) hfs_btree_inc_height() argument
459 if (tree->root) { hfs_btree_inc_height()
460 node = hfs_bnode_find(tree, tree->root); hfs_btree_inc_height()
464 new_node = hfs_bmap_alloc(tree); hfs_btree_inc_height()
470 tree->root = new_node->this; hfs_btree_inc_height()
471 if (!tree->depth) { hfs_btree_inc_height()
472 tree->leaf_head = tree->leaf_tail = new_node->this; hfs_btree_inc_height()
482 new_node->height = ++tree->depth; hfs_btree_inc_height()
492 rec = tree->node_size - 2; hfs_btree_inc_height()
497 node->parent = tree->root; hfs_btree_inc_height()
499 tree->attributes & HFS_TREE_VARIDXKEYS) hfs_btree_inc_height()
502 key_size = tree->max_key_len + 1; hfs_btree_inc_height()
505 if (!(tree->attributes & HFS_TREE_VARIDXKEYS)) { hfs_btree_inc_height()
506 key_size = tree->max_key_len + 1; hfs_btree_inc_height()
507 hfs_bnode_write_u8(new_node, 14, tree->max_key_len); hfs_btree_inc_height()
519 mark_inode_dirty(tree->inode); hfs_btree_inc_height()
H A Dbfind.c14 int hfs_find_init(struct hfs_btree *tree, struct hfs_find_data *fd) hfs_find_init() argument
18 fd->tree = tree; hfs_find_init()
20 ptr = kmalloc(tree->max_key_len * 2 + 4, GFP_KERNEL); hfs_find_init()
24 fd->key = ptr + tree->max_key_len + 2; hfs_find_init()
26 tree->cnid, __builtin_return_address(0)); hfs_find_init()
27 mutex_lock(&tree->tree_lock); hfs_find_init()
36 fd->tree->cnid, __builtin_return_address(0)); hfs_find_exit()
37 mutex_unlock(&fd->tree->tree_lock); hfs_find_exit()
38 fd->tree = NULL; hfs_find_exit()
62 cmpval = bnode->tree->keycmp(fd->key, fd->search_key); __hfs_brec_find()
96 struct hfs_btree *tree; hfs_brec_find() local
102 tree = fd->tree; hfs_brec_find()
106 nidx = tree->root; hfs_brec_find()
109 height = tree->depth; hfs_brec_find()
113 bnode = hfs_bnode_find(tree, nidx); hfs_brec_find()
163 struct hfs_btree *tree; hfs_brec_goto() local
169 tree = bnode->tree; hfs_brec_goto()
182 bnode = hfs_bnode_find(tree, idx); hfs_brec_goto()
200 bnode = hfs_bnode_find(tree, idx); hfs_brec_goto()
H A Dbtree.h46 struct hfs_btree *tree; member in struct:hfs_bnode
72 struct hfs_btree *tree; member in struct:hfs_find_data
134 #define HFS_NODE_HEADER 0x01 /* The tree header node (node 0) */
139 __be16 depth; /* (V) The number of levels in this B-tree */
156 #define BTREE_ATTR_BADCLOSE 0x00000001 /* b-tree not closed properly. not
162 b-tree but not in extents
163 b-tree (hfsplus). */
H A Dhfs.h43 #define HFS_EXT_CNID 3 /* EXTents B-tree */
44 #define HFS_CAT_CNID 4 /* CATalog B-tree */
148 /* The key used in the catalog b-tree: */
156 /* The key used in the extents b-tree: */
232 /* A catalog tree record */
263 __be32 drXTClpSiz; /* clumpsize for the extents B-tree */
264 __be32 drCTClpSiz; /* clumpsize for the catalog B-tree */
275 __be32 drXTFlSize; /* bytes in the extents B-tree */
276 hfs_extent_rec drXTExtRec; /* extents B-tree's first 3 extents */
277 __be32 drCTFlSize; /* bytes in the catalog B-tree */
278 hfs_extent_rec drCTExtRec; /* catalog B-tree's first 3 extents */
H A Dinode.c74 struct hfs_btree *tree; hfs_releasepage() local
81 tree = HFS_SB(sb)->ext_tree; hfs_releasepage()
84 tree = HFS_SB(sb)->cat_tree; hfs_releasepage()
91 if (!tree) hfs_releasepage()
94 if (tree->node_size >= PAGE_CACHE_SIZE) { hfs_releasepage()
95 nidx = page->index >> (tree->node_size_shift - PAGE_CACHE_SHIFT); hfs_releasepage()
96 spin_lock(&tree->hash_lock); hfs_releasepage()
97 node = hfs_bnode_findhash(tree, nidx); hfs_releasepage()
106 spin_unlock(&tree->hash_lock); hfs_releasepage()
108 nidx = page->index << (PAGE_CACHE_SHIFT - tree->node_size_shift); hfs_releasepage()
109 i = 1 << (PAGE_CACHE_SHIFT - tree->node_size_shift); hfs_releasepage()
110 spin_lock(&tree->hash_lock); hfs_releasepage()
112 node = hfs_bnode_findhash(tree, nidx++); hfs_releasepage()
121 } while (--i && nidx < tree->node_count); hfs_releasepage()
122 spin_unlock(&tree->hash_lock); hfs_releasepage()
376 * the catalog B-tree and the 'type' of the desired file return the
/linux-4.1.27/fs/hfsplus/
H A Dbtree.c41 * Catalog B-tree Header
46 * Attributes B-tree Header
134 struct hfs_btree *tree; hfs_btree_open() local
141 tree = kzalloc(sizeof(*tree), GFP_KERNEL); hfs_btree_open()
142 if (!tree) hfs_btree_open()
145 mutex_init(&tree->tree_lock); hfs_btree_open()
146 spin_lock_init(&tree->hash_lock); hfs_btree_open()
147 tree->sb = sb; hfs_btree_open()
148 tree->cnid = id; hfs_btree_open()
152 tree->inode = inode; hfs_btree_open()
154 if (!HFSPLUS_I(tree->inode)->first_blocks) { hfs_btree_open()
159 mapping = tree->inode->i_mapping; hfs_btree_open()
167 tree->root = be32_to_cpu(head->root); hfs_btree_open()
168 tree->leaf_count = be32_to_cpu(head->leaf_count); hfs_btree_open()
169 tree->leaf_head = be32_to_cpu(head->leaf_head); hfs_btree_open()
170 tree->leaf_tail = be32_to_cpu(head->leaf_tail); hfs_btree_open()
171 tree->node_count = be32_to_cpu(head->node_count); hfs_btree_open()
172 tree->free_nodes = be32_to_cpu(head->free_nodes); hfs_btree_open()
173 tree->attributes = be32_to_cpu(head->attributes); hfs_btree_open()
174 tree->node_size = be16_to_cpu(head->node_size); hfs_btree_open()
175 tree->max_key_len = be16_to_cpu(head->max_key_len); hfs_btree_open()
176 tree->depth = be16_to_cpu(head->depth); hfs_btree_open()
178 /* Verify the tree and set the correct compare function */ hfs_btree_open()
181 if (tree->max_key_len != HFSPLUS_EXT_KEYLEN - sizeof(u16)) { hfs_btree_open()
183 tree->max_key_len); hfs_btree_open()
186 if (tree->attributes & HFS_TREE_VARIDXKEYS) { hfs_btree_open()
191 tree->keycmp = hfsplus_ext_cmp_key; hfs_btree_open()
194 if (tree->max_key_len != HFSPLUS_CAT_KEYLEN - sizeof(u16)) { hfs_btree_open()
196 tree->max_key_len); hfs_btree_open()
199 if (!(tree->attributes & HFS_TREE_VARIDXKEYS)) { hfs_btree_open()
206 tree->keycmp = hfsplus_cat_bin_cmp_key; hfs_btree_open()
208 tree->keycmp = hfsplus_cat_case_cmp_key; hfs_btree_open()
213 if (tree->max_key_len != HFSPLUS_ATTR_KEYLEN - sizeof(u16)) { hfs_btree_open()
215 tree->max_key_len); hfs_btree_open()
218 tree->keycmp = hfsplus_attr_bin_cmp_key; hfs_btree_open()
225 if (!(tree->attributes & HFS_TREE_BIGKEYS)) { hfs_btree_open()
230 size = tree->node_size; hfs_btree_open()
233 if (!tree->node_count) hfs_btree_open()
236 tree->node_size_shift = ffs(size) - 1; hfs_btree_open()
238 tree->pages_per_bnode = hfs_btree_open()
239 (tree->node_size + PAGE_CACHE_SIZE - 1) >> hfs_btree_open()
244 return tree; hfs_btree_open()
249 tree->inode->i_mapping->a_ops = &hfsplus_aops; hfs_btree_open()
250 iput(tree->inode); hfs_btree_open()
252 kfree(tree); hfs_btree_open()
257 void hfs_btree_close(struct hfs_btree *tree) hfs_btree_close() argument
262 if (!tree) hfs_btree_close()
266 while ((node = tree->node_hash[i])) { hfs_btree_close()
267 tree->node_hash[i] = node->next_hash; hfs_btree_close()
271 node->tree->cnid, node->this, hfs_btree_close()
274 tree->node_hash_cnt--; hfs_btree_close()
277 iput(tree->inode); hfs_btree_close()
278 kfree(tree); hfs_btree_close()
281 int hfs_btree_write(struct hfs_btree *tree) hfs_btree_write() argument
287 node = hfs_bnode_find(tree, 0); hfs_btree_write()
296 head->root = cpu_to_be32(tree->root); hfs_btree_write()
297 head->leaf_count = cpu_to_be32(tree->leaf_count); hfs_btree_write()
298 head->leaf_head = cpu_to_be32(tree->leaf_head); hfs_btree_write()
299 head->leaf_tail = cpu_to_be32(tree->leaf_tail); hfs_btree_write()
300 head->node_count = cpu_to_be32(tree->node_count); hfs_btree_write()
301 head->free_nodes = cpu_to_be32(tree->free_nodes); hfs_btree_write()
302 head->attributes = cpu_to_be32(tree->attributes); hfs_btree_write()
303 head->depth = cpu_to_be16(tree->depth); hfs_btree_write()
313 struct hfs_btree *tree = prev->tree; hfs_bmap_new_bmap() local
318 node = hfs_bnode_create(tree, idx); hfs_bmap_new_bmap()
322 tree->free_nodes--; hfs_bmap_new_bmap()
329 hfs_bnode_clear(node, 0, tree->node_size); hfs_bmap_new_bmap()
338 hfs_bnode_write_u16(node, tree->node_size - 2, 14); hfs_bmap_new_bmap()
339 hfs_bnode_write_u16(node, tree->node_size - 4, tree->node_size - 6); hfs_bmap_new_bmap()
344 struct hfs_bnode *hfs_bmap_alloc(struct hfs_btree *tree) hfs_bmap_alloc() argument
355 while (!tree->free_nodes) { hfs_bmap_alloc()
356 struct inode *inode = tree->inode; hfs_bmap_alloc()
361 res = hfsplus_file_extend(inode, hfs_bnode_need_zeroout(tree)); hfs_bmap_alloc()
366 HFSPLUS_SB(tree->sb)->alloc_blksz_shift; hfs_bmap_alloc()
368 hip->alloc_blocks << HFSPLUS_SB(tree->sb)->fs_shift; hfs_bmap_alloc()
370 count = inode->i_size >> tree->node_size_shift; hfs_bmap_alloc()
371 tree->free_nodes = count - tree->node_count; hfs_bmap_alloc()
372 tree->node_count = count; hfs_bmap_alloc()
376 node = hfs_bnode_find(tree, nidx); hfs_bmap_alloc()
398 tree->free_nodes--; hfs_bmap_alloc()
399 mark_inode_dirty(tree->inode); hfs_bmap_alloc()
401 return hfs_bnode_create(tree, hfs_bmap_alloc()
420 next_node = hfs_bnode_find(tree, nidx); hfs_bmap_alloc()
437 struct hfs_btree *tree; hfs_bmap_free() local
445 tree = node->tree; hfs_bmap_free()
447 node = hfs_bnode_find(tree, 0); hfs_bmap_free()
464 node = hfs_bnode_find(tree, i); hfs_bmap_free()
495 tree->free_nodes++; hfs_bmap_free()
496 mark_inode_dirty(tree->inode); hfs_bmap_free()
H A Dbnode.c60 struct hfs_btree *tree; hfs_bnode_read_key() local
63 tree = node->tree; hfs_bnode_read_key()
65 tree->attributes & HFS_TREE_VARIDXKEYS || hfs_bnode_read_key()
66 node->tree->cnid == HFSPLUS_ATTR_CNID) hfs_bnode_read_key()
69 key_len = tree->max_key_len + 2; hfs_bnode_read_key()
129 struct hfs_btree *tree; hfs_bnode_copy() local
136 tree = src_node->tree; hfs_bnode_copy()
311 off = node->tree->node_size - 2; hfs_bnode_dump()
318 if (node->tree->attributes & HFS_TREE_VARIDXKEYS || hfs_bnode_dump()
319 node->tree->cnid == HFSPLUS_ATTR_CNID) hfs_bnode_dump()
322 tmp = node->tree->max_key_len + 2; hfs_bnode_dump()
338 struct hfs_btree *tree; hfs_bnode_unlink() local
342 tree = node->tree; hfs_bnode_unlink()
344 tmp = hfs_bnode_find(tree, node->prev); hfs_bnode_unlink()
353 tree->leaf_head = node->next; hfs_bnode_unlink()
356 tmp = hfs_bnode_find(tree, node->next); hfs_bnode_unlink()
365 tree->leaf_tail = node->prev; hfs_bnode_unlink()
371 tree->root = 0; hfs_bnode_unlink()
372 tree->depth = 0; hfs_bnode_unlink()
384 struct hfs_bnode *hfs_bnode_findhash(struct hfs_btree *tree, u32 cnid) hfs_bnode_findhash() argument
388 if (cnid >= tree->node_count) { hfs_bnode_findhash()
394 for (node = tree->node_hash[hfs_bnode_hash(cnid)]; hfs_bnode_findhash()
401 static struct hfs_bnode *__hfs_bnode_create(struct hfs_btree *tree, u32 cnid) __hfs_bnode_create() argument
410 if (cnid >= tree->node_count) { __hfs_bnode_create()
416 sb = tree->inode->i_sb; __hfs_bnode_create()
417 size = sizeof(struct hfs_bnode) + tree->pages_per_bnode * __hfs_bnode_create()
422 node->tree = tree; __hfs_bnode_create()
427 node->tree->cnid, node->this); __hfs_bnode_create()
429 spin_lock(&tree->hash_lock); __hfs_bnode_create()
430 node2 = hfs_bnode_findhash(tree, cnid); __hfs_bnode_create()
433 node->next_hash = tree->node_hash[hash]; __hfs_bnode_create()
434 tree->node_hash[hash] = node; __hfs_bnode_create()
435 tree->node_hash_cnt++; __hfs_bnode_create()
437 spin_unlock(&tree->hash_lock); __hfs_bnode_create()
443 spin_unlock(&tree->hash_lock); __hfs_bnode_create()
445 mapping = tree->inode->i_mapping; __hfs_bnode_create()
446 off = (loff_t)cnid << tree->node_size_shift; __hfs_bnode_create()
449 for (i = 0; i < tree->pages_per_bnode; block++, i++) { __hfs_bnode_create()
471 node->tree->cnid, node->this, atomic_read(&node->refcnt)); hfs_bnode_unhash()
472 for (p = &node->tree->node_hash[hfs_bnode_hash(node->this)]; hfs_bnode_unhash()
477 node->tree->node_hash_cnt--; hfs_bnode_unhash()
480 /* Load a particular node out of a tree */ hfs_bnode_find()
481 struct hfs_bnode *hfs_bnode_find(struct hfs_btree *tree, u32 num) hfs_bnode_find() argument
488 spin_lock(&tree->hash_lock); hfs_bnode_find()
489 node = hfs_bnode_findhash(tree, num); hfs_bnode_find()
492 spin_unlock(&tree->hash_lock); hfs_bnode_find()
499 spin_unlock(&tree->hash_lock); hfs_bnode_find()
500 node = __hfs_bnode_create(tree, num); hfs_bnode_find()
528 if (node->height <= 1 || node->height > tree->depth) hfs_bnode_find()
535 rec_off = tree->node_size - 2; hfs_bnode_find()
543 next_off > tree->node_size || hfs_bnode_find()
570 for (i = 0; i < node->tree->pages_per_bnode; i++) hfs_bnode_free()
576 struct hfs_bnode *hfs_bnode_create(struct hfs_btree *tree, u32 num) hfs_bnode_create() argument
582 spin_lock(&tree->hash_lock); hfs_bnode_create()
583 node = hfs_bnode_findhash(tree, num); hfs_bnode_create()
584 spin_unlock(&tree->hash_lock); hfs_bnode_create()
590 node = __hfs_bnode_create(tree, num); hfs_bnode_create()
600 min_t(int, PAGE_CACHE_SIZE, tree->node_size)); hfs_bnode_create()
603 for (i = 1; i < tree->pages_per_bnode; i++) { hfs_bnode_create()
619 node->tree->cnid, node->this, hfs_bnode_get()
628 struct hfs_btree *tree = node->tree; hfs_bnode_put() local
632 node->tree->cnid, node->this, hfs_bnode_put()
635 if (!atomic_dec_and_lock(&node->refcnt, &tree->hash_lock)) hfs_bnode_put()
637 for (i = 0; i < tree->pages_per_bnode; i++) { hfs_bnode_put()
645 spin_unlock(&tree->hash_lock); hfs_bnode_put()
646 if (hfs_bnode_need_zeroout(tree)) hfs_bnode_put()
647 hfs_bnode_clear(node, 0, tree->node_size); hfs_bnode_put()
652 spin_unlock(&tree->hash_lock); hfs_bnode_put()
657 * Unused nodes have to be zeroed if this is the catalog tree and
660 bool hfs_bnode_need_zeroout(struct hfs_btree *tree) hfs_bnode_need_zeroout() argument
662 struct super_block *sb = tree->inode->i_sb; hfs_bnode_need_zeroout()
666 return tree->cnid == HFSPLUS_CAT_CNID && hfs_bnode_need_zeroout()
H A Dbrec.c24 dataoff = node->tree->node_size - (rec + 2) * 2; hfs_brec_lenoff()
39 !(node->tree->attributes & HFS_TREE_VARIDXKEYS) && hfs_brec_keylen()
40 (node->tree->cnid != HFSPLUS_ATTR_CNID)) { hfs_brec_keylen()
41 retval = node->tree->max_key_len + 2; hfs_brec_keylen()
44 node->tree->node_size - (rec + 1) * 2); hfs_brec_keylen()
47 if (recoff > node->tree->node_size - 2) { hfs_brec_keylen()
53 if (retval > node->tree->max_key_len + 2) { hfs_brec_keylen()
64 struct hfs_btree *tree; hfs_brec_insert() local
71 tree = fd->tree; hfs_brec_insert()
73 if (!tree->root) hfs_brec_insert()
74 hfs_btree_inc_height(tree); hfs_brec_insert()
75 fd->bnode = hfs_bnode_find(tree, tree->leaf_head); hfs_brec_insert()
90 end_rec_off = tree->node_size - (node->num_recs + 1) * 2; hfs_brec_insert()
104 tree->leaf_count++; hfs_brec_insert()
105 mark_inode_dirty(tree->inode); hfs_brec_insert()
115 idx_rec_off = tree->node_size - (rec + 1) * 2; hfs_brec_insert()
146 hfs_btree_inc_height(tree); hfs_brec_insert()
147 new_node->parent = tree->root; hfs_brec_insert()
149 fd->bnode = hfs_bnode_find(tree, new_node->parent); hfs_brec_insert()
163 if ((tree->attributes & HFS_TREE_VARIDXKEYS) || hfs_brec_insert()
164 (tree->cnid == HFSPLUS_ATTR_CNID)) hfs_brec_insert()
168 cpu_to_be16(tree->max_key_len); hfs_brec_insert()
169 key_len = tree->max_key_len + 2; hfs_brec_insert()
179 struct hfs_btree *tree; hfs_brec_remove() local
183 tree = fd->tree; hfs_brec_remove()
186 rec_off = tree->node_size - (fd->record + 2) * 2; hfs_brec_remove()
187 end_off = tree->node_size - (node->num_recs + 1) * 2; hfs_brec_remove()
190 tree->leaf_count--; hfs_brec_remove()
191 mark_inode_dirty(tree->inode); hfs_brec_remove()
200 parent = hfs_bnode_find(tree, node->parent); hfs_brec_remove()
235 struct hfs_btree *tree; hfs_bnode_split() local
241 tree = fd->tree; hfs_bnode_split()
243 new_node = hfs_bmap_alloc(tree); hfs_bnode_split()
256 next_node = hfs_bnode_find(tree, node->next); hfs_bnode_split()
266 size = tree->node_size / 2 - node->num_recs * 2 - 14; hfs_bnode_split()
267 old_rec_off = tree->node_size - 4; hfs_bnode_split()
302 new_rec_off = tree->node_size - 2; hfs_bnode_split()
341 } else if (node->this == tree->leaf_tail) { hfs_bnode_split()
343 tree->leaf_tail = new_node->this; hfs_bnode_split()
344 mark_inode_dirty(tree->inode); hfs_bnode_split()
356 struct hfs_btree *tree; hfs_brec_update_parent() local
362 tree = fd->tree; hfs_brec_update_parent()
369 parent = hfs_bnode_find(tree, node->parent); hfs_brec_update_parent()
379 if ((tree->attributes & HFS_TREE_VARIDXKEYS) || hfs_brec_update_parent()
380 (tree->cnid == HFSPLUS_ATTR_CNID)) hfs_brec_update_parent()
383 fd->keylength = newkeylen = tree->max_key_len + 2; hfs_brec_update_parent()
387 rec_off = tree->node_size - (rec + 2) * 2; hfs_brec_update_parent()
388 end_rec_off = tree->node_size - (parent->num_recs + 1) * 2; hfs_brec_update_parent()
403 rec_off = tree->node_size - (rec + 2) * 2; hfs_brec_update_parent()
404 end_rec_off = tree->node_size - hfs_brec_update_parent()
430 fd->bnode = hfs_bnode_find(tree, new_node->parent); hfs_brec_update_parent()
455 static int hfs_btree_inc_height(struct hfs_btree *tree) hfs_btree_inc_height() argument
463 if (tree->root) { hfs_btree_inc_height()
464 node = hfs_bnode_find(tree, tree->root); hfs_btree_inc_height()
468 new_node = hfs_bmap_alloc(tree); hfs_btree_inc_height()
474 tree->root = new_node->this; hfs_btree_inc_height()
475 if (!tree->depth) { hfs_btree_inc_height()
476 tree->leaf_head = tree->leaf_tail = new_node->this; hfs_btree_inc_height()
486 new_node->height = ++tree->depth; hfs_btree_inc_height()
496 rec = tree->node_size - 2; hfs_btree_inc_height()
501 node->parent = tree->root; hfs_btree_inc_height()
503 tree->attributes & HFS_TREE_VARIDXKEYS || hfs_btree_inc_height()
504 tree->cnid == HFSPLUS_ATTR_CNID) hfs_btree_inc_height()
507 key_size = tree->max_key_len + 2; hfs_btree_inc_height()
510 if (!(tree->attributes & HFS_TREE_VARIDXKEYS) && hfs_btree_inc_height()
511 (tree->cnid != HFSPLUS_ATTR_CNID)) { hfs_btree_inc_height()
512 key_size = tree->max_key_len + 2; hfs_btree_inc_height()
513 hfs_bnode_write_u16(new_node, 14, tree->max_key_len); hfs_btree_inc_height()
524 mark_inode_dirty(tree->inode); hfs_btree_inc_height()
H A Dbfind.c14 int hfs_find_init(struct hfs_btree *tree, struct hfs_find_data *fd) hfs_find_init() argument
18 fd->tree = tree; hfs_find_init()
20 ptr = kmalloc(tree->max_key_len * 2 + 4, GFP_KERNEL); hfs_find_init()
24 fd->key = ptr + tree->max_key_len + 2; hfs_find_init()
26 tree->cnid, __builtin_return_address(0)); hfs_find_init()
27 switch (tree->cnid) { hfs_find_init()
29 mutex_lock_nested(&tree->tree_lock, CATALOG_BTREE_MUTEX); hfs_find_init()
32 mutex_lock_nested(&tree->tree_lock, EXTENTS_BTREE_MUTEX); hfs_find_init()
35 mutex_lock_nested(&tree->tree_lock, ATTR_BTREE_MUTEX); hfs_find_init()
48 fd->tree->cnid, __builtin_return_address(0)); hfs_find_exit()
49 mutex_unlock(&fd->tree->tree_lock); hfs_find_exit()
50 fd->tree = NULL; hfs_find_exit()
62 if (bnode->tree->cnid == HFSPLUS_EXT_CNID) { hfs_find_1st_rec_by_cnid()
65 } else if (bnode->tree->cnid == HFSPLUS_CAT_CNID) { hfs_find_1st_rec_by_cnid()
68 } else if (bnode->tree->cnid == HFSPLUS_ATTR_CNID) { hfs_find_1st_rec_by_cnid()
99 cmpval = bnode->tree->keycmp(fd->key, fd->search_key); hfs_find_rec_by_key()
165 struct hfs_btree *tree; hfs_brec_find() local
171 tree = fd->tree; hfs_brec_find()
175 nidx = tree->root; hfs_brec_find()
178 height = tree->depth; hfs_brec_find()
182 bnode = hfs_bnode_find(tree, nidx); hfs_brec_find()
232 struct hfs_btree *tree; hfs_brec_goto() local
238 tree = bnode->tree; hfs_brec_goto()
251 bnode = hfs_bnode_find(tree, idx); hfs_brec_goto()
269 bnode = hfs_bnode_find(tree, idx); hfs_brec_goto()
H A Dinode.c69 struct hfs_btree *tree; hfsplus_releasepage() local
76 tree = HFSPLUS_SB(sb)->ext_tree; hfsplus_releasepage()
79 tree = HFSPLUS_SB(sb)->cat_tree; hfsplus_releasepage()
82 tree = HFSPLUS_SB(sb)->attr_tree; hfsplus_releasepage()
88 if (!tree) hfsplus_releasepage()
90 if (tree->node_size >= PAGE_CACHE_SIZE) { hfsplus_releasepage()
92 (tree->node_size_shift - PAGE_CACHE_SHIFT); hfsplus_releasepage()
93 spin_lock(&tree->hash_lock); hfsplus_releasepage()
94 node = hfs_bnode_findhash(tree, nidx); hfsplus_releasepage()
103 spin_unlock(&tree->hash_lock); hfsplus_releasepage()
106 (PAGE_CACHE_SHIFT - tree->node_size_shift); hfsplus_releasepage()
107 i = 1 << (PAGE_CACHE_SHIFT - tree->node_size_shift); hfsplus_releasepage()
108 spin_lock(&tree->hash_lock); hfsplus_releasepage()
110 node = hfs_bnode_findhash(tree, nidx++); hfsplus_releasepage()
119 } while (--i && nidx < tree->node_count); hfsplus_releasepage()
120 spin_unlock(&tree->hash_lock); hfsplus_releasepage()
317 pr_err("sync non-existent attributes tree\n"); hfsplus_file_fsync()
H A Dhfsplus_fs.h65 /* B-tree mutex nested subclasses */
104 struct hfs_btree *tree; member in struct:hfs_bnode
256 #define HFSPLUS_I_CAT_DIRTY 1 /* has changes in the catalog tree */
257 #define HFSPLUS_I_EXT_DIRTY 2 /* has changes in the extent tree */
259 #define HFSPLUS_I_ATTR_DIRTY 4 /* has changes in the attributes tree */
287 struct hfs_btree *tree; member in struct:hfs_find_data
395 void hfs_btree_close(struct hfs_btree *tree);
396 int hfs_btree_write(struct hfs_btree *tree);
397 struct hfs_bnode *hfs_bmap_alloc(struct hfs_btree *tree);
413 struct hfs_bnode *hfs_bnode_findhash(struct hfs_btree *tree, u32 cnid);
415 struct hfs_bnode *hfs_bnode_find(struct hfs_btree *tree, u32 num);
417 struct hfs_bnode *hfs_bnode_create(struct hfs_btree *tree, u32 num);
420 bool hfs_bnode_need_zeroout(struct hfs_btree *tree);
429 int hfs_find_init(struct hfs_btree *tree, struct hfs_find_data *fd);
H A Dhfsplus_raw.h161 #define HFS_NODE_HEADER 0x01 /* The tree header node (node 0) */
198 #define HFSPLUS_EXT_CNID 3 /* EXTents B-tree */
199 #define HFSPLUS_CAT_CNID 4 /* CATalog B-tree */
323 /* A data record in the catalog tree */
337 /* HFS+ extents tree key */
355 /* HFS+ attributes tree key */
391 /* A data record in the attributes tree */
/linux-4.1.27/kernel/
H A Daudit_tree.c47 * the same tree.
54 * tree.chunks anchors chunk.owners[].list hash_lock
55 * tree.rules anchors rule.rlist audit_filter_mutex
56 * chunk.trees anchors tree.same_root hash_lock
60 * tree is refcounted; one reference for "some rules on rules_list refer to
76 struct audit_tree *tree; alloc_tree() local
78 tree = kmalloc(sizeof(struct audit_tree) + strlen(s) + 1, GFP_KERNEL); alloc_tree()
79 if (tree) { alloc_tree()
80 atomic_set(&tree->count, 1); alloc_tree()
81 tree->goner = 0; alloc_tree()
82 INIT_LIST_HEAD(&tree->chunks); alloc_tree()
83 INIT_LIST_HEAD(&tree->rules); alloc_tree()
84 INIT_LIST_HEAD(&tree->list); alloc_tree()
85 INIT_LIST_HEAD(&tree->same_root); alloc_tree()
86 tree->root = NULL; alloc_tree()
87 strcpy(tree->pathname, s); alloc_tree()
89 return tree; alloc_tree()
92 static inline void get_tree(struct audit_tree *tree) get_tree() argument
94 atomic_inc(&tree->count); get_tree()
97 static inline void put_tree(struct audit_tree *tree) put_tree() argument
99 if (atomic_dec_and_test(&tree->count)) put_tree()
100 kfree_rcu(tree, head); put_tree()
104 const char *audit_tree_path(struct audit_tree *tree) audit_tree_path() argument
106 return tree->pathname; audit_tree_path()
200 int audit_tree_match(struct audit_chunk *chunk, struct audit_tree *tree) audit_tree_match() argument
204 if (chunk->owners[n].owner == tree) audit_tree_match()
317 static int create_chunk(struct inode *inode, struct audit_tree *tree) create_chunk() argument
332 if (tree->goner) { create_chunk()
341 chunk->owners[0].owner = tree; create_chunk()
342 get_tree(tree); create_chunk()
343 list_add(&chunk->owners[0].list, &tree->chunks); create_chunk()
344 if (!tree->root) { create_chunk()
345 tree->root = chunk; create_chunk()
346 list_add(&tree->same_root, &chunk->trees); create_chunk()
355 /* the first tagged inode becomes root of tree */ tag_chunk()
356 static int tag_chunk(struct inode *inode, struct audit_tree *tree) tag_chunk() argument
366 return create_chunk(inode, tree); tag_chunk()
373 if (old->owners[n].owner == tree) { tag_chunk()
411 if (tree->goner) { tag_chunk()
434 p->owner = tree; tag_chunk()
435 get_tree(tree); tag_chunk()
436 list_add(&p->list, &tree->chunks); tag_chunk()
441 if (!tree->root) { tag_chunk()
442 tree->root = chunk; tag_chunk()
443 list_add(&tree->same_root, &chunk->trees); tag_chunk()
464 audit_log_untrustedstring(ab, rule->tree->pathname); audit_tree_log_remove_rule()
470 static void kill_rules(struct audit_tree *tree) kill_rules() argument
475 list_for_each_entry_safe(rule, next, &tree->rules, rlist) { kill_rules()
479 if (rule->tree) { kill_rules()
482 rule->tree = NULL; kill_rules()
507 /* trim the uncommitted chunks from tree */
509 static void trim_marked(struct audit_tree *tree) trim_marked() argument
513 if (tree->goner) { trim_marked()
518 for (p = tree->chunks.next; p != &tree->chunks; p = q) { trim_marked()
523 list_add(p, &tree->chunks); trim_marked()
527 while (!list_empty(&tree->chunks)) { trim_marked()
530 node = list_entry(tree->chunks.next, struct node, list); trim_marked()
538 if (!tree->root && !tree->goner) { trim_marked()
539 tree->goner = 1; trim_marked()
542 kill_rules(tree); trim_marked()
543 list_del_init(&tree->list); trim_marked()
545 prune_one(tree); trim_marked()
556 struct audit_tree *tree; audit_remove_tree_rule() local
557 tree = rule->tree; audit_remove_tree_rule()
558 if (tree) { audit_remove_tree_rule()
561 if (list_empty(&tree->rules) && !tree->goner) { audit_remove_tree_rule()
562 tree->root = NULL; audit_remove_tree_rule()
563 list_del_init(&tree->same_root); audit_remove_tree_rule()
564 tree->goner = 1; audit_remove_tree_rule()
565 list_move(&tree->list, &prune_list); audit_remove_tree_rule()
566 rule->tree = NULL; audit_remove_tree_rule()
571 rule->tree = NULL; audit_remove_tree_rule()
590 struct audit_tree *tree; audit_trim_trees() local
596 tree = container_of(cursor.next, struct audit_tree, list); audit_trim_trees()
597 get_tree(tree); audit_trim_trees()
599 list_add(&cursor, &tree->list); audit_trim_trees()
602 err = kern_path(tree->pathname, 0, &path); audit_trim_trees()
612 list_for_each_entry(node, &tree->chunks, list) { audit_trim_trees()
621 trim_marked(tree); audit_trim_trees()
624 put_tree(tree); audit_trim_trees()
637 rule->inode_f || rule->watch || rule->tree) audit_make_tree()
639 rule->tree = alloc_tree(pathname); audit_make_tree()
640 if (!rule->tree) audit_make_tree()
645 void audit_put_tree(struct audit_tree *tree) audit_put_tree() argument
647 put_tree(tree); audit_put_tree()
709 struct audit_tree *seed = rule->tree, *tree; audit_add_tree_rule() local
714 rule->tree = NULL; audit_add_tree_rule()
715 list_for_each_entry(tree, &tree_list, list) { audit_add_tree_rule()
716 if (!strcmp(seed->pathname, tree->pathname)) { audit_add_tree_rule()
718 rule->tree = tree; audit_add_tree_rule()
719 list_add(&rule->rlist, &tree->rules); audit_add_tree_rule()
723 tree = seed; audit_add_tree_rule()
724 list_add(&tree->list, &tree_list); audit_add_tree_rule()
725 list_add(&rule->rlist, &tree->rules); audit_add_tree_rule()
726 /* do not set rule->tree yet */ audit_add_tree_rule()
735 err = kern_path(tree->pathname, 0, &path); audit_add_tree_rule()
745 get_tree(tree); audit_add_tree_rule()
746 err = iterate_mounts(tag_mount, tree, mnt); audit_add_tree_rule()
752 list_for_each_entry(node, &tree->chunks, list) audit_add_tree_rule()
756 trim_marked(tree); audit_add_tree_rule()
762 put_tree(tree); audit_add_tree_rule()
765 rule->tree = tree; audit_add_tree_rule()
766 put_tree(tree); audit_add_tree_rule()
771 list_del_init(&tree->list); audit_add_tree_rule()
772 list_del_init(&tree->rules); audit_add_tree_rule()
773 put_tree(tree); audit_add_tree_rule()
804 struct audit_tree *tree; audit_tag_tree() local
807 tree = container_of(cursor.next, struct audit_tree, list); audit_tag_tree()
808 get_tree(tree); audit_tag_tree()
810 list_add(&cursor, &tree->list); audit_tag_tree()
813 err = kern_path(tree->pathname, 0, &path2); audit_tag_tree()
820 put_tree(tree); audit_tag_tree()
825 failed = iterate_mounts(tag_mount, tree, tagged); audit_tag_tree()
827 put_tree(tree); audit_tag_tree()
834 if (!tree->goner) { audit_tag_tree()
835 list_del(&tree->list); audit_tag_tree()
836 list_add(&tree->list, &tree_list); audit_tag_tree()
839 put_tree(tree); audit_tag_tree()
843 struct audit_tree *tree; audit_tag_tree() local
845 tree = container_of(barrier.prev, struct audit_tree, list); audit_tag_tree()
846 get_tree(tree); audit_tag_tree()
847 list_del(&tree->list); audit_tag_tree()
848 list_add(&tree->list, &barrier); audit_tag_tree()
854 list_for_each_entry(node, &tree->chunks, list) audit_tag_tree()
858 trim_marked(tree); audit_tag_tree()
861 put_tree(tree); audit_tag_tree()
H A Dauditfilter.c166 krule->inode_f || krule->watch || krule->tree || audit_to_inode()
554 if (entry->rule.tree) audit_data_to_entry()
555 audit_put_tree(entry->rule.tree); /* that's the temporary one */ audit_data_to_entry()
614 audit_tree_path(krule->tree)); audit_krule_to_data()
674 if (strcmp(audit_tree_path(a->tree), audit_compare_rule()
675 audit_tree_path(b->tree))) audit_compare_rule()
773 * never dereferences tree and we can't get false positives there audit_dupe_rule()
778 new->tree = old->tree; audit_dupe_rule()
864 struct audit_tree *tree = entry->rule.tree; audit_add_rule() local
882 if (tree) audit_add_rule()
883 audit_put_tree(tree); audit_add_rule()
896 if (tree) audit_add_rule()
897 audit_put_tree(tree); audit_add_rule()
901 if (tree) { audit_add_rule()
949 struct audit_tree *tree = entry->rule.tree; audit_del_rule() local
972 if (e->rule.tree) audit_del_rule()
991 if (tree) audit_del_rule()
992 audit_put_tree(tree); /* that's the temporary one */ audit_del_rule()
1383 if (r->watch || r->tree) update_lsm_rule()
/linux-4.1.27/drivers/usb/misc/sisusbvga/
H A DMakefile2 # Makefile for the sisusb driver (if driver is inside kernel tree).
/linux-4.1.27/scripts/dtc/
H A Dfstree.c31 struct node *tree; read_fstree() local
37 tree = build_node(NULL, NULL); read_fstree()
64 add_property(tree, prop); read_fstree()
72 add_child(tree, newchild); read_fstree()
79 return tree; read_fstree()
84 struct node *tree; dt_from_fs() local
86 tree = read_fstree(dirname); dt_from_fs()
87 tree = name_node(tree, ""); dt_from_fs()
89 return build_boot_info(NULL, tree, guess_boot_cpuid(tree)); dt_from_fs()
H A Ddtc.c33 static void fill_fullpaths(struct node *tree, const char *prefix) fill_fullpaths() argument
38 tree->fullpath = join_path(prefix, tree->name); fill_fullpaths()
40 unit = strchr(tree->name, '@'); fill_fullpaths()
42 tree->basenamelen = unit - tree->name; fill_fullpaths()
44 tree->basenamelen = strlen(tree->name); fill_fullpaths()
46 for_each_child(tree, child) fill_fullpaths()
47 fill_fullpaths(child, tree->fullpath); fill_fullpaths()
77 "\t\tdts - device tree source text\n"
78 "\t\tdtb - device tree blob\n"
79 "\t\tfs - /proc/device-tree style directory",
82 "\t\tdts - device tree source text\n"
83 "\t\tdtb - device tree blob\n"
91 "\n\tTry to produce output even if the input tree has errors",
H A Dlivetree.c339 struct node *tree, uint32_t boot_cpuid_phys) build_boot_info()
345 bi->dt = tree; build_boot_info()
380 struct property *get_property_by_label(struct node *tree, const char *label, get_property_by_label() argument
386 *node = tree; get_property_by_label()
388 for_each_property(tree, prop) { for_each_property()
396 for_each_child(tree, c) { for_each_child()
406 struct marker *get_marker_label(struct node *tree, const char *label, get_marker_label() argument
413 *node = tree; get_marker_label()
415 for_each_property(tree, p) { for_each_property()
423 for_each_child(tree, c) { for_each_child()
445 struct node *get_node_by_path(struct node *tree, const char *path) get_node_by_path() argument
451 if (tree->deleted) get_node_by_path()
453 return tree; get_node_by_path()
461 for_each_child(tree, child) { for_each_child()
471 struct node *get_node_by_label(struct node *tree, const char *label) get_node_by_label() argument
478 for_each_label(tree->labels, l) get_node_by_label()
480 return tree; get_node_by_label()
482 for_each_child(tree, child) { for_each_child()
491 struct node *get_node_by_phandle(struct node *tree, cell_t phandle) get_node_by_phandle() argument
497 if (tree->phandle == phandle) { get_node_by_phandle()
498 if (tree->deleted) get_node_by_phandle()
500 return tree; get_node_by_phandle()
503 for_each_child(tree, child) { for_each_child()
512 struct node *get_node_by_ref(struct node *tree, const char *ref) get_node_by_ref() argument
515 return get_node_by_path(tree, ref); get_node_by_ref()
517 return get_node_by_label(tree, ref); get_node_by_ref()
551 uint32_t guess_boot_cpuid(struct node *tree) guess_boot_cpuid() argument
556 cpus = get_node_by_path(tree, "/cpus"); guess_boot_cpuid()
338 build_boot_info(struct reserve_info *reservelist, struct node *tree, uint32_t boot_cpuid_phys) build_boot_info() argument
H A Dtreesource.c41 die("Unable to parse input tree\n"); dt_from_source()
44 die("Syntax error parsing input tree\n"); dt_from_source()
236 static void write_tree_source_node(FILE *f, struct node *tree, int level) write_tree_source_node() argument
243 for_each_label(tree->labels, l) write_tree_source_node()
245 if (tree->name && (*tree->name)) write_tree_source_node()
246 fprintf(f, "%s {\n", tree->name); write_tree_source_node()
250 for_each_property(tree, prop) { for_each_property()
257 for_each_child(tree, child) { for_each_child()
H A Dflattree.c258 static void flatten_tree(struct node *tree, struct emitter *emit, flatten_tree() argument
266 if (tree->deleted) flatten_tree()
269 emit->beginnode(etarget, tree->labels); flatten_tree()
272 emit->string(etarget, tree->fullpath, 0); flatten_tree()
274 emit->string(etarget, tree->name, 0); flatten_tree()
278 for_each_property(tree, prop) { for_each_property()
299 emit->cell(etarget, tree->basenamelen+1);
302 if ((vi->flags & FTF_VARALIGN) && ((tree->basenamelen+1) >= 8))
305 emit->string(etarget, tree->name, tree->basenamelen);
309 for_each_child(tree, child) { for_each_child()
313 emit->endnode(etarget, tree->labels);
385 die("Unknown device tree blob version %d\n", version); dt_to_blob()
419 * the device tree itself, and finally the strings. dt_to_blob()
436 die("Error writing device tree blob: %s\n", dt_to_blob()
439 die("Short write on device tree blob\n"); dt_to_blob()
476 die("Unknown device tree blob version %d\n", version); dt_to_asm()
594 die("Premature end of data parsing flat device tree\n"); flat_read_chunk()
618 die("Premature end of data parsing flat device tree\n"); flat_realign()
629 die("Premature end of data parsing flat device tree\n"); flat_read_string()
768 fprintf(stderr, "Warning: Flat tree input has " unflatten_tree()
783 die("Premature FDT_END in device tree blob\n"); unflatten_tree()
788 fprintf(stderr, "Warning: NOP tag found in flat tree" unflatten_tree()
795 die("Invalid opcode word %08x in device tree blob\n", unflatten_tree()
817 struct node *tree; dt_from_blob() local
920 die("Device tree blob doesn't begin with FDT_BEGIN_NODE (begins with 0x%08x)\n", val); dt_from_blob()
922 tree = unflatten_tree(&dtbuf, &strbuf, "", flags); dt_from_blob()
926 die("Device tree blob doesn't end with FDT_END\n"); dt_from_blob()
932 return build_boot_info(reservelist, tree, boot_cpuid_phys); dt_from_blob()
H A Ddtc.h208 struct property *get_property_by_label(struct node *tree, const char *label,
210 struct marker *get_marker_label(struct node *tree, const char *label,
213 struct node *get_node_by_path(struct node *tree, const char *path);
214 struct node *get_node_by_label(struct node *tree, const char *label);
215 struct node *get_node_by_phandle(struct node *tree, cell_t phandle);
216 struct node *get_node_by_ref(struct node *tree, const char *ref);
219 uint32_t guess_boot_cpuid(struct node *tree);
221 /* Boot info (tree plus memreserve information */
240 struct node *dt; /* the device tree */
245 struct node *tree, uint32_t boot_cpuid_phys);
/linux-4.1.27/lib/zlib_deflate/
H A Ddeftree.c13 * Each code tree is stored in a compressed form which is itself
88 /* The static literal tree. Since the bit lengths are imposed, there is no
90 * The codes 286 and 287 are needed to build a canonical tree (see zlib_tr_init
95 /* The static distance tree. (Actually a trivial tree since all codes use
115 const ct_data *static_tree; /* static tree or NULL */
118 int elems; /* max number of elements in the tree */
137 static void pqdownheap (deflate_state *s, ct_data *tree, int k);
139 static void gen_codes (ct_data *tree, int max_code, ush *bl_count);
141 static void scan_tree (deflate_state *s, ct_data *tree, int max_code);
142 static void send_tree (deflate_state *s, ct_data *tree, int max_code);
156 # define send_code(s, c, tree) send_bits(s, tree[c].Code, tree[c].Len)
157 /* Send a code of the given tree. c and tree must not have side effects */
160 # define send_code(s, c, tree) \
162 send_bits(s, tree[c].Code, tree[c].Len); }
228 int n; /* iterates over tree elements */ tr_static_init()
234 /* number of codes at each bit length for an optimal tree */ tr_static_init()
271 /* Construct the codes of the static literal tree */ tr_static_init()
279 * tree construction to get a canonical Huffman tree (longest code tr_static_init()
284 /* The static distance tree is trivial: */ tr_static_init()
293 * Initialize the tree data structures for a new zlib stream.
330 int n; /* iterates over tree elements */ init_block()
343 /* Index within the heap array of least frequent node in the Huffman tree */
350 #define pqremove(s, tree, top) \
354 pqdownheap(s, tree, SMALLEST); \
358 * Compares to subtrees, using the tree depth as tie breaker when
361 #define smaller(tree, n, m, depth) \
362 (tree[n].Freq < tree[m].Freq || \
363 (tree[n].Freq == tree[m].Freq && depth[n] <= depth[m]))
366 * Restore the heap property by moving down the tree starting at node k,
373 ct_data *tree, /* the tree to restore */ pqdownheap()
382 smaller(tree, s->heap[j+1], s->heap[j], s->depth)) { pqdownheap()
386 if (smaller(tree, v, s->heap[j], s->depth)) break; pqdownheap()
391 /* And continue down the tree, setting j to the left son of k */ pqdownheap()
398 * Compute the optimal bit lengths for a tree and update the total bit length
401 * above are the tree nodes sorted by increasing frequency.
409 tree_desc *desc /* the tree descriptor */ gen_bitlen()
412 ct_data *tree = desc->dyn_tree; gen_bitlen() local
419 int n, m; /* iterate over the tree elements */ gen_bitlen()
428 * overflow in the case of the bit length tree). gen_bitlen()
430 tree[s->heap[s->heap_max]].Len = 0; /* root of the heap */ gen_bitlen()
434 bits = tree[tree[n].Dad].Len + 1; gen_bitlen()
436 tree[n].Len = (ush)bits; gen_bitlen()
437 /* We overwrite tree[n].Dad which is no longer needed */ gen_bitlen()
444 f = tree[n].Freq; gen_bitlen()
457 s->bl_count[bits]--; /* move one leaf down the tree */ gen_bitlen()
476 if (tree[m].Len != (unsigned) bits) { gen_bitlen()
477 Trace((stderr,"code %d bits %d->%d\n", m, tree[m].Len, bits)); gen_bitlen()
478 s->opt_len += ((long)bits - (long)tree[m].Len) gen_bitlen()
479 *(long)tree[m].Freq; gen_bitlen()
480 tree[m].Len = (ush)bits; gen_bitlen()
488 * Generate the codes for a given tree and bit counts (which need not be
491 * the given tree and the field len is set for all tree elements.
492 * OUT assertion: the field code is set for all tree elements of non
496 ct_data *tree, /* the tree to decorate */ gen_codes()
520 int len = tree[n].Len; gen_codes()
523 tree[n].Code = bi_reverse(next_code[len]++, len); gen_codes()
525 Tracecv(tree != static_ltree, (stderr,"\nn %3d %c l %2d c %4x (%x) ", gen_codes()
526 n, (isgraph(n) ? n : ' '), len, tree[n].Code, next_code[len]-1)); gen_codes()
531 * Construct one Huffman tree and assigns the code bit strings and lengths.
533 * IN assertion: the field freq is set for all tree elements.
540 tree_desc *desc /* the tree descriptor */ build_tree()
543 ct_data *tree = desc->dyn_tree; build_tree() local
557 if (tree[n].Freq != 0) { build_tree()
561 tree[n].Len = 0; build_tree()
572 tree[node].Freq = 1; build_tree()
579 /* The elements heap[heap_len/2+1 .. heap_len] are leaves of the tree, build_tree()
582 for (n = s->heap_len/2; n >= 1; n--) pqdownheap(s, tree, n); build_tree()
584 /* Construct the Huffman tree by repeatedly combining the least two build_tree()
587 node = elems; /* next internal node of the tree */ build_tree()
589 pqremove(s, tree, n); /* n = node of least frequency */ build_tree()
596 tree[node].Freq = tree[n].Freq + tree[m].Freq; build_tree()
598 tree[n].Dad = tree[m].Dad = (ush)node; build_tree()
600 if (tree == s->bl_tree) { build_tree()
602 node, tree[node].Freq, n, tree[n].Freq, m, tree[m].Freq); build_tree()
607 pqdownheap(s, tree, SMALLEST); build_tree()
619 gen_codes ((ct_data *)tree, max_code, s->bl_count); build_tree()
623 * Scan a literal or distance tree to determine the frequencies of the codes
624 * in the bit length tree.
628 ct_data *tree, /* the tree to be scanned */ scan_tree()
632 int n; /* iterates over all tree elements */ scan_tree()
635 int nextlen = tree[0].Len; /* length of next code */ scan_tree()
641 tree[max_code+1].Len = (ush)0xffff; /* guard */ scan_tree()
644 curlen = nextlen; nextlen = tree[n+1].Len; scan_tree()
669 * Send a literal or distance tree in compressed form, using the codes in
674 ct_data *tree, /* the tree to be scanned */ send_tree()
678 int n; /* iterates over all tree elements */ send_tree()
681 int nextlen = tree[0].Len; /* length of next code */ send_tree()
686 /* tree[max_code+1].Len = -1; */ /* guard already set */ send_tree()
690 curlen = nextlen; nextlen = tree[n+1].Len; send_tree()
721 * Construct the Huffman tree for the bit lengths and return the index in
734 /* Build the bit length tree: */ build_bl_tree()
736 /* opt_len now includes the length of the tree representations, except build_bl_tree()
747 /* Update opt_len to include the bit length tree and counts */ build_bl_tree()
757 * lengths of the bit length codes, the literal tree and the distance tree.
762 int lcodes, /* number of codes for each tree */ send_all_trees()
763 int dcodes, /* number of codes for each tree */ send_all_trees()
764 int blcodes /* number of codes for each tree */ send_all_trees()
780 Tracev((stderr, "\nbl tree: sent %ld", s->bits_sent)); send_all_trees()
782 send_tree(s, (ct_data *)s->dyn_ltree, lcodes-1); /* literal tree */ send_all_trees()
783 Tracev((stderr, "\nlit tree: sent %ld", s->bits_sent)); send_all_trees()
785 send_tree(s, (ct_data *)s->dyn_dtree, dcodes-1); /* distance tree */ send_all_trees()
786 Tracev((stderr, "\ndist tree: sent %ld", s->bits_sent)); send_all_trees()
881 * the compressed block data, excluding the tree representations.
884 /* Build the bit length tree for the above two trees, and get the index
1020 ct_data *ltree, /* literal tree */ compress_block()
1021 ct_data *dtree /* distance tree */ compress_block()
371 pqdownheap( deflate_state *s, ct_data *tree, int k ) pqdownheap() argument
495 gen_codes( ct_data *tree, int max_code, ush *bl_count ) gen_codes() argument
626 scan_tree( deflate_state *s, ct_data *tree, int max_code ) scan_tree() argument
672 send_tree( deflate_state *s, ct_data *tree, int max_code ) send_tree() argument
H A Ddefutil.h46 ush dad; /* father node in Huffman tree */
59 ct_data *dyn_tree; /* the dynamic tree */
61 static_tree_desc *stat_desc; /* the corresponding static tree */
168 struct ct_data_s dyn_ltree[HEAP_SIZE]; /* literal and length tree */
169 struct ct_data_s dyn_dtree[2*D_CODES+1]; /* distance tree */
170 struct ct_data_s bl_tree[2*BL_CODES+1]; /* Huffman tree for bit lengths */
172 struct tree_desc_s l_desc; /* desc. for literal tree */
173 struct tree_desc_s d_desc; /* desc. for distance tree */
174 struct tree_desc_s bl_desc; /* desc. for bit length tree */
177 /* number of codes at each bit length for an optimal tree */
/linux-4.1.27/fs/btrfs/
H A Dextent_map.c28 * extent_map_tree_init - initialize extent map tree
29 * @tree: tree to initialize
31 * Initialize the extent tree @tree. Should be called for each new inode
34 void extent_map_tree_init(struct extent_map_tree *tree) extent_map_tree_init() argument
36 tree->map = RB_ROOT; extent_map_tree_init()
37 INIT_LIST_HEAD(&tree->modified_extents); extent_map_tree_init()
38 rwlock_init(&tree->lock); extent_map_tree_init()
137 * search through the tree for an extent_map with a given offset. If
225 static void try_merge_map(struct extent_map_tree *tree, struct extent_map *em) try_merge_map() argument
244 rb_erase(&merge->rb_node, &tree->map); try_merge_map()
256 rb_erase(&merge->rb_node, &tree->map); try_merge_map()
266 * @tree: tree to unpin the extent in
275 int unpin_extent_cache(struct extent_map_tree *tree, u64 start, u64 len, unpin_extent_cache() argument
282 write_lock(&tree->lock); unpin_extent_cache()
283 em = lookup_extent_mapping(tree, start, len); unpin_extent_cache()
300 try_merge_map(tree, em); unpin_extent_cache()
309 write_unlock(&tree->lock); unpin_extent_cache()
314 void clear_em_logging(struct extent_map_tree *tree, struct extent_map *em) clear_em_logging() argument
318 try_merge_map(tree, em); clear_em_logging()
321 static inline void setup_extent_mapping(struct extent_map_tree *tree, setup_extent_mapping() argument
330 list_move(&em->list, &tree->modified_extents); setup_extent_mapping()
332 try_merge_map(tree, em); setup_extent_mapping()
336 * add_extent_mapping - add new extent map to the extent tree
337 * @tree: tree to insert new map in
340 * Insert @em into @tree or perform a simple forward/backward merge with
342 * into the tree directly, with an additional reference taken, or a
345 int add_extent_mapping(struct extent_map_tree *tree, add_extent_mapping() argument
350 ret = tree_insert(&tree->map, em); add_extent_mapping()
354 setup_extent_mapping(tree, em, modified); add_extent_mapping()
360 __lookup_extent_mapping(struct extent_map_tree *tree, __lookup_extent_mapping() argument
369 rb_node = __tree_search(&tree->map, start, &prev, &next); __lookup_extent_mapping()
390 * @tree: tree to lookup in
394 * Find and return the first extent_map struct in @tree that intersects the
395 * [start, len] range. There may be additional objects in the tree that
399 struct extent_map *lookup_extent_mapping(struct extent_map_tree *tree, lookup_extent_mapping() argument
402 return __lookup_extent_mapping(tree, start, len, 1); lookup_extent_mapping()
407 * @tree: tree to lookup in
411 * Find and return the first extent_map struct in @tree that intersects the
416 struct extent_map *search_extent_mapping(struct extent_map_tree *tree, search_extent_mapping() argument
419 return __lookup_extent_mapping(tree, start, len, 0); search_extent_mapping()
423 * remove_extent_mapping - removes an extent_map from the extent tree
424 * @tree: extent tree to remove from
427 * Removes @em from @tree. No reference counts are dropped, and no checks
430 int remove_extent_mapping(struct extent_map_tree *tree, struct extent_map *em) remove_extent_mapping() argument
435 rb_erase(&em->rb_node, &tree->map); remove_extent_mapping()
442 void replace_extent_mapping(struct extent_map_tree *tree, replace_extent_mapping() argument
451 rb_replace_node(&cur->rb_node, &new->rb_node, &tree->map); replace_extent_mapping()
454 setup_extent_mapping(tree, new, modified); replace_extent_mapping()
H A Dextent_map.h66 void extent_map_tree_init(struct extent_map_tree *tree);
67 struct extent_map *lookup_extent_mapping(struct extent_map_tree *tree,
69 int add_extent_mapping(struct extent_map_tree *tree,
71 int remove_extent_mapping(struct extent_map_tree *tree, struct extent_map *em);
72 void replace_extent_mapping(struct extent_map_tree *tree,
81 int unpin_extent_cache(struct extent_map_tree *tree, u64 start, u64 len, u64 gen);
82 void clear_em_logging(struct extent_map_tree *tree, struct extent_map *em);
83 struct extent_map *search_extent_mapping(struct extent_map_tree *tree,
H A Dextent_io.c67 pr_err("BTRFS: state leak: start %llu end %llu state %u in tree %d refs %d\n", btrfs_leak_debug_check()
85 #define btrfs_debug_check_extent_io_range(tree, start, end) \
86 __btrfs_debug_check_extent_io_range(__func__, (tree), (start), (end)) __btrfs_debug_check_extent_io_range()
88 struct extent_io_tree *tree, u64 start, u64 end) __btrfs_debug_check_extent_io_range()
93 if (!tree->mapping) __btrfs_debug_check_extent_io_range()
96 inode = tree->mapping->host; __btrfs_debug_check_extent_io_range()
121 struct extent_io_tree *tree; member in struct:extent_page_data
136 tree_fs_info(struct extent_io_tree *tree) tree_fs_info() argument
138 if (!tree->mapping) tree_fs_info()
140 return btrfs_sb(tree->mapping->host->i_sb); tree_fs_info()
198 void extent_io_tree_init(struct extent_io_tree *tree, extent_io_tree_init() argument
201 tree->state = RB_ROOT; extent_io_tree_init()
202 tree->ops = NULL; extent_io_tree_init()
203 tree->dirty_bytes = 0; extent_io_tree_init()
204 spin_lock_init(&tree->lock); extent_io_tree_init()
205 tree->mapping = mapping; extent_io_tree_init()
273 static struct rb_node *__etree_search(struct extent_io_tree *tree, u64 offset, __etree_search() argument
279 struct rb_root *root = &tree->state; __etree_search()
326 tree_search_for_insert(struct extent_io_tree *tree, tree_search_for_insert() argument
334 ret = __etree_search(tree, offset, &prev, NULL, p_ret, parent_ret); tree_search_for_insert()
340 static inline struct rb_node *tree_search(struct extent_io_tree *tree, tree_search() argument
343 return tree_search_for_insert(tree, offset, NULL, NULL); tree_search()
346 static void merge_cb(struct extent_io_tree *tree, struct extent_state *new, merge_cb() argument
349 if (tree->ops && tree->ops->merge_extent_hook) merge_cb()
350 tree->ops->merge_extent_hook(tree->mapping->host, new, merge_cb()
357 * extent in the tree. Extents with EXTENT_IO in their state field
361 * This should be called with the tree lock held.
363 static void merge_state(struct extent_io_tree *tree, merge_state() argument
377 merge_cb(tree, state, other); merge_state()
379 rb_erase(&other->rb_node, &tree->state); merge_state()
389 merge_cb(tree, state, other); merge_state()
391 rb_erase(&other->rb_node, &tree->state); merge_state()
398 static void set_state_cb(struct extent_io_tree *tree, set_state_cb() argument
401 if (tree->ops && tree->ops->set_bit_hook) set_state_cb()
402 tree->ops->set_bit_hook(tree->mapping->host, state, bits); set_state_cb()
405 static void clear_state_cb(struct extent_io_tree *tree, clear_state_cb() argument
408 if (tree->ops && tree->ops->clear_bit_hook) clear_state_cb()
409 tree->ops->clear_bit_hook(tree->mapping->host, state, bits); clear_state_cb()
412 static void set_state_bits(struct extent_io_tree *tree,
416 * insert an extent_state struct into the tree. 'bits' are set on the
422 * The tree lock is not taken internally. This is a utility function and
425 static int insert_state(struct extent_io_tree *tree, insert_state() argument
439 set_state_bits(tree, state, bits); insert_state()
441 node = tree_insert(&tree->state, NULL, end, &state->rb_node, p, parent); insert_state()
450 merge_state(tree, state); insert_state()
454 static void split_cb(struct extent_io_tree *tree, struct extent_state *orig, split_cb() argument
457 if (tree->ops && tree->ops->split_extent_hook) split_cb()
458 tree->ops->split_extent_hook(tree->mapping->host, orig, split); split_cb()
467 * the tree has 'orig' at [orig->start, orig->end]. After calling, there
468 * are two extent state structs in the tree:
472 * The tree locks are not taken by this function. They need to be held
475 static int split_state(struct extent_io_tree *tree, struct extent_state *orig, split_state() argument
480 split_cb(tree, orig, split); split_state()
487 node = tree_insert(&tree->state, &orig->rb_node, prealloc->end, split_state()
510 * struct is freed and removed from the tree
512 static struct extent_state *clear_state_bit(struct extent_io_tree *tree, clear_state_bit() argument
521 WARN_ON(range > tree->dirty_bytes); clear_state_bit()
522 tree->dirty_bytes -= range; clear_state_bit()
524 clear_state_cb(tree, state, bits); clear_state_bit()
531 rb_erase(&state->rb_node, &tree->state); clear_state_bit()
538 merge_state(tree, state); clear_state_bit()
553 static void extent_io_tree_panic(struct extent_io_tree *tree, int err) extent_io_tree_panic() argument
555 btrfs_panic(tree_fs_info(tree), err, "Locking error: " extent_io_tree_panic()
556 "Extent tree was modified by another " extent_io_tree_panic()
561 * clear some bits on a range in the tree. This may require splitting
562 * or inserting elements in the tree, so the gfp mask is used to
566 * the given range from the tree regardless of state (ie for truncate).
570 * This takes the tree lock, and returns 0 on success and < 0 on error.
572 int clear_extent_bit(struct extent_io_tree *tree, u64 start, u64 end, clear_extent_bit() argument
585 btrfs_debug_check_extent_io_range(tree, start, end); clear_extent_bit()
601 * is the case if we only have in the tree extent states that clear_extent_bit()
608 spin_lock(&tree->lock); clear_extent_bit()
631 node = tree_search(tree, start); clear_extent_bit()
666 err = split_state(tree, state, prealloc, start); clear_extent_bit()
668 extent_io_tree_panic(tree, err); clear_extent_bit()
674 state = clear_state_bit(tree, state, &bits, wake); clear_extent_bit()
688 err = split_state(tree, state, prealloc, end + 1); clear_extent_bit()
690 extent_io_tree_panic(tree, err); clear_extent_bit()
695 clear_state_bit(tree, prealloc, &bits, wake); clear_extent_bit()
701 state = clear_state_bit(tree, state, &bits, wake); clear_extent_bit()
711 spin_unlock(&tree->lock); clear_extent_bit()
720 spin_unlock(&tree->lock); clear_extent_bit()
726 static void wait_on_state(struct extent_io_tree *tree,
728 __releases(tree->lock)
729 __acquires(tree->lock)
733 spin_unlock(&tree->lock);
735 spin_lock(&tree->lock);
740 * waits for one or more bits to clear on a range in the state tree.
742 * The tree lock is taken by this function
744 static void wait_extent_bit(struct extent_io_tree *tree, u64 start, u64 end, wait_extent_bit() argument
750 btrfs_debug_check_extent_io_range(tree, start, end); wait_extent_bit()
752 spin_lock(&tree->lock); wait_extent_bit()
759 node = tree_search(tree, start); wait_extent_bit()
772 wait_on_state(tree, state); wait_extent_bit()
781 if (!cond_resched_lock(&tree->lock)) { wait_extent_bit()
787 spin_unlock(&tree->lock); wait_extent_bit()
790 static void set_state_bits(struct extent_io_tree *tree, set_state_bits() argument
796 set_state_cb(tree, state, bits); set_state_bits()
799 tree->dirty_bytes += range; set_state_bits()
824 * set some bits on a range in the tree. This may require allocations or
831 * [start, end] is inclusive This takes the tree lock.
835 __set_extent_bit(struct extent_io_tree *tree, u64 start, u64 end, __set_extent_bit() argument
849 btrfs_debug_check_extent_io_range(tree, start, end); __set_extent_bit()
858 spin_lock(&tree->lock); __set_extent_bit()
871 node = tree_search_for_insert(tree, start, &p, &parent); __set_extent_bit()
875 err = insert_state(tree, prealloc, start, end, __set_extent_bit()
878 extent_io_tree_panic(tree, err); __set_extent_bit()
902 set_state_bits(tree, state, &bits); __set_extent_bit()
904 merge_state(tree, state); __set_extent_bit()
940 err = split_state(tree, state, prealloc, start); __set_extent_bit()
942 extent_io_tree_panic(tree, err); __set_extent_bit()
948 set_state_bits(tree, state, &bits); __set_extent_bit()
950 merge_state(tree, state); __set_extent_bit()
982 err = insert_state(tree, prealloc, start, this_end, __set_extent_bit()
985 extent_io_tree_panic(tree, err); __set_extent_bit()
1007 err = split_state(tree, state, prealloc, end + 1); __set_extent_bit()
1009 extent_io_tree_panic(tree, err); __set_extent_bit()
1011 set_state_bits(tree, prealloc, &bits); __set_extent_bit()
1013 merge_state(tree, prealloc); __set_extent_bit()
1021 spin_unlock(&tree->lock); __set_extent_bit()
1030 spin_unlock(&tree->lock); __set_extent_bit()
1036 int set_extent_bit(struct extent_io_tree *tree, u64 start, u64 end, set_extent_bit() argument
1040 return __set_extent_bit(tree, start, end, bits, 0, failed_start, set_extent_bit()
1048 * @tree: the io tree to search
1062 int convert_extent_bit(struct extent_io_tree *tree, u64 start, u64 end, convert_extent_bit() argument
1076 btrfs_debug_check_extent_io_range(tree, start, end); convert_extent_bit()
1085 * after locking the tree. convert_extent_bit()
1092 spin_lock(&tree->lock); convert_extent_bit()
1106 node = tree_search_for_insert(tree, start, &p, &parent); convert_extent_bit()
1113 err = insert_state(tree, prealloc, start, end, convert_extent_bit()
1116 extent_io_tree_panic(tree, err); convert_extent_bit()
1133 set_state_bits(tree, state, &bits); convert_extent_bit()
1135 state = clear_state_bit(tree, state, &clear_bits, 0); convert_extent_bit()
1167 err = split_state(tree, state, prealloc, start); convert_extent_bit()
1169 extent_io_tree_panic(tree, err); convert_extent_bit()
1174 set_state_bits(tree, state, &bits); convert_extent_bit()
1176 state = clear_state_bit(tree, state, &clear_bits, 0); convert_extent_bit()
1210 err = insert_state(tree, prealloc, start, this_end, convert_extent_bit()
1213 extent_io_tree_panic(tree, err); convert_extent_bit()
1232 err = split_state(tree, state, prealloc, end + 1); convert_extent_bit()
1234 extent_io_tree_panic(tree, err); convert_extent_bit()
1236 set_state_bits(tree, prealloc, &bits); convert_extent_bit()
1238 clear_state_bit(tree, prealloc, &clear_bits, 0); convert_extent_bit()
1246 spin_unlock(&tree->lock); convert_extent_bit()
1255 spin_unlock(&tree->lock); convert_extent_bit()
1263 int set_extent_dirty(struct extent_io_tree *tree, u64 start, u64 end, set_extent_dirty() argument
1266 return set_extent_bit(tree, start, end, EXTENT_DIRTY, NULL, set_extent_dirty()
1270 int set_extent_bits(struct extent_io_tree *tree, u64 start, u64 end, set_extent_bits() argument
1273 return set_extent_bit(tree, start, end, bits, NULL, set_extent_bits()
1277 int clear_extent_bits(struct extent_io_tree *tree, u64 start, u64 end, clear_extent_bits() argument
1280 return clear_extent_bit(tree, start, end, bits, 0, 0, NULL, mask); clear_extent_bits()
1283 int set_extent_delalloc(struct extent_io_tree *tree, u64 start, u64 end, set_extent_delalloc() argument
1286 return set_extent_bit(tree, start, end, set_extent_delalloc()
1291 int set_extent_defrag(struct extent_io_tree *tree, u64 start, u64 end, set_extent_defrag() argument
1294 return set_extent_bit(tree, start, end, set_extent_defrag()
1299 int clear_extent_dirty(struct extent_io_tree *tree, u64 start, u64 end, clear_extent_dirty() argument
1302 return clear_extent_bit(tree, start, end, clear_extent_dirty()
1307 int set_extent_new(struct extent_io_tree *tree, u64 start, u64 end, set_extent_new() argument
1310 return set_extent_bit(tree, start, end, EXTENT_NEW, NULL, set_extent_new()
1314 int set_extent_uptodate(struct extent_io_tree *tree, u64 start, u64 end, set_extent_uptodate() argument
1317 return set_extent_bit(tree, start, end, EXTENT_UPTODATE, NULL, set_extent_uptodate()
1321 int clear_extent_uptodate(struct extent_io_tree *tree, u64 start, u64 end, clear_extent_uptodate() argument
1324 return clear_extent_bit(tree, start, end, EXTENT_UPTODATE, 0, 0, clear_extent_uptodate()
1332 int lock_extent_bits(struct extent_io_tree *tree, u64 start, u64 end, lock_extent_bits() argument
1339 err = __set_extent_bit(tree, start, end, EXTENT_LOCKED | bits, lock_extent_bits()
1343 wait_extent_bit(tree, failed_start, end, EXTENT_LOCKED); lock_extent_bits()
1352 int lock_extent(struct extent_io_tree *tree, u64 start, u64 end) lock_extent() argument
1354 return lock_extent_bits(tree, start, end, 0, NULL); lock_extent()
1357 int try_lock_extent(struct extent_io_tree *tree, u64 start, u64 end) try_lock_extent() argument
1362 err = __set_extent_bit(tree, start, end, EXTENT_LOCKED, EXTENT_LOCKED, try_lock_extent()
1366 clear_extent_bit(tree, start, failed_start - 1, try_lock_extent()
1373 int unlock_extent_cached(struct extent_io_tree *tree, u64 start, u64 end, unlock_extent_cached() argument
1376 return clear_extent_bit(tree, start, end, EXTENT_LOCKED, 1, 0, cached, unlock_extent_cached()
1380 int unlock_extent(struct extent_io_tree *tree, u64 start, u64 end) unlock_extent() argument
1382 return clear_extent_bit(tree, start, end, EXTENT_LOCKED, 1, 0, NULL, unlock_extent()
1420 * helper function to set both pages and extents in the tree writeback
1422 static int set_range_writeback(struct extent_io_tree *tree, u64 start, u64 end) set_range_writeback() argument
1429 page = find_get_page(tree->mapping, index); set_range_writeback()
1439 * return it. tree->lock must be held. NULL will returned if
1443 find_first_extent_bit_state(struct extent_io_tree *tree, find_first_extent_bit_state() argument
1453 node = tree_search(tree, start); find_first_extent_bit_state()
1471 * find the first offset in the io tree with 'bits' set. zero is
1477 int find_first_extent_bit(struct extent_io_tree *tree, u64 start, find_first_extent_bit() argument
1485 spin_lock(&tree->lock); find_first_extent_bit()
1505 state = find_first_extent_bit_state(tree, start, bits); find_first_extent_bit()
1514 spin_unlock(&tree->lock); find_first_extent_bit()
1522 * 1 is returned if we find something, 0 if nothing was in the tree
1524 static noinline u64 find_delalloc_range(struct extent_io_tree *tree, find_delalloc_range() argument
1534 spin_lock(&tree->lock); find_delalloc_range()
1540 node = tree_search(tree, cur_start); find_delalloc_range()
1574 spin_unlock(&tree->lock); find_delalloc_range()
1673 * 1 is returned if we find something, 0 if nothing was in the tree
1676 struct extent_io_tree *tree, find_lock_delalloc_range()
1691 found = find_delalloc_range(tree, &delalloc_start, &delalloc_end, find_lock_delalloc_range()
1735 lock_extent_bits(tree, delalloc_start, delalloc_end, 0, &cached_state); find_lock_delalloc_range()
1738 ret = test_range_bit(tree, delalloc_start, delalloc_end, find_lock_delalloc_range()
1741 unlock_extent_cached(tree, delalloc_start, delalloc_end, find_lock_delalloc_range()
1760 struct extent_io_tree *tree = &BTRFS_I(inode)->io_tree; extent_clear_unlock_delalloc() local
1768 clear_extent_bit(tree, start, end, clear_bits, 1, 0, NULL, GFP_NOFS); extent_clear_unlock_delalloc()
1808 * count the number of bytes in the tree that have a given bit(s)
1812 u64 count_range_bits(struct extent_io_tree *tree, count_range_bits() argument
1826 spin_lock(&tree->lock); count_range_bits()
1828 total_bytes = tree->dirty_bytes; count_range_bits()
1835 node = tree_search(tree, cur_start); count_range_bits()
1863 spin_unlock(&tree->lock); count_range_bits()
1868 * set the private field for a given byte offset in the tree. If there isn't
1871 static int set_state_private(struct extent_io_tree *tree, u64 start, u64 private) set_state_private() argument
1877 spin_lock(&tree->lock); set_state_private()
1882 node = tree_search(tree, start); set_state_private()
1894 spin_unlock(&tree->lock); set_state_private()
1898 int get_state_private(struct extent_io_tree *tree, u64 start, u64 *private) get_state_private() argument
1904 spin_lock(&tree->lock); get_state_private()
1909 node = tree_search(tree, start); get_state_private()
1921 spin_unlock(&tree->lock); get_state_private()
1926 * searches a range in the state tree for a given mask.
1927 * If 'filled' == 1, this returns 1 only if every extent in the tree
1931 int test_range_bit(struct extent_io_tree *tree, u64 start, u64 end, test_range_bit() argument
1938 spin_lock(&tree->lock); test_range_bit()
1943 node = tree_search(tree, start); test_range_bit()
1977 spin_unlock(&tree->lock); test_range_bit()
1983 * extents in the tree for that page are up to date
1985 static void check_page_uptodate(struct extent_io_tree *tree, struct page *page) check_page_uptodate() argument
1989 if (test_range_bit(tree, start, end, EXTENT_UPTODATE, 1, NULL)) check_page_uptodate()
2109 * each time an IO finishes, we do a fast check in the IO failure tree
2210 struct extent_io_tree *tree = &BTRFS_I(inode)->io_tree; btrfs_get_io_failure_record() local
2260 /* set the bits in the private failure tree */ btrfs_get_io_failure_record()
2266 /* set the bits in the inode's tree */ btrfs_get_io_failure_record()
2268 ret = set_extent_bits(tree, start, end, EXTENT_DAMAGED, btrfs_get_io_failure_record()
2403 struct extent_io_tree *tree = &BTRFS_I(inode)->io_tree; bio_readpage_error() local
2438 ret = tree->ops->submit_bio_hook(inode, read_mode, bio, bio_readpage_error()
2454 struct extent_io_tree *tree; end_extent_writepage() local
2457 tree = &BTRFS_I(page->mapping->host)->io_tree; end_extent_writepage()
2459 if (tree->ops && tree->ops->writepage_end_io_hook) { end_extent_writepage()
2460 ret = tree->ops->writepage_end_io_hook(page, start, end_extent_writepage()
2478 * clear the writeback bits in the extent tree for this IO
2481 * Scheduling is not allowed, so the extent state tree is expected
2524 endio_readpage_release_extent(struct extent_io_tree *tree, u64 start, u64 len, endio_readpage_release_extent() argument
2530 if (uptodate && tree->track_uptodate) endio_readpage_release_extent()
2531 set_extent_uptodate(tree, start, end, &cached, GFP_ATOMIC); endio_readpage_release_extent()
2532 unlock_extent_cached(tree, start, end, &cached, GFP_ATOMIC); endio_readpage_release_extent()
2539 * set the page up to date if all extents in the tree are uptodate
2540 * clear the lock bit in the extent tree
2543 * Scheduling is not allowed, so the extent state tree is expected
2551 struct extent_io_tree *tree; end_bio_extent_readpage() local
2572 tree = &BTRFS_I(inode)->io_tree; bio_for_each_segment_all()
2596 if (likely(uptodate && tree->ops && bio_for_each_segment_all()
2597 tree->ops->readpage_end_io_hook)) { bio_for_each_segment_all()
2598 ret = tree->ops->readpage_end_io_hook(io_bio, offset, bio_for_each_segment_all()
2610 if (tree->ops && tree->ops->readpage_io_failed_hook) { bio_for_each_segment_all()
2611 ret = tree->ops->readpage_io_failed_hook(page, mirror); bio_for_each_segment_all()
2657 endio_readpage_release_extent(tree, bio_for_each_segment_all()
2663 endio_readpage_release_extent(tree, start, bio_for_each_segment_all()
2671 endio_readpage_release_extent(tree, extent_start, bio_for_each_segment_all()
2679 endio_readpage_release_extent(tree, extent_start, extent_len,
2755 struct extent_io_tree *tree = bio->bi_private; submit_one_bio() local
2764 if (tree->ops && tree->ops->submit_bio_hook) submit_one_bio()
2765 ret = tree->ops->submit_bio_hook(page->mapping->host, rw, bio, submit_one_bio()
2776 static int merge_bio(int rw, struct extent_io_tree *tree, struct page *page, merge_bio() argument
2781 if (tree->ops && tree->ops->merge_bio_hook) merge_bio()
2782 ret = tree->ops->merge_bio_hook(rw, page, offset, size, bio, merge_bio()
2789 static int submit_extent_page(int rw, struct extent_io_tree *tree, submit_extent_page() argument
2818 merge_bio(rw, tree, page, offset, page_size, bio, bio_flags) || submit_extent_page()
2842 bio->bi_private = tree; submit_extent_page()
2902 * into the tree that are removed when the IO is done (by the end_io
2906 static int __do_readpage(struct extent_io_tree *tree, __do_readpage() argument
2941 unlock_extent(tree, start, end); __do_readpage()
2971 set_extent_uptodate(tree, cur, cur + iosize - 1, __do_readpage()
2974 unlock_extent_cached(tree, cur, __do_readpage()
2984 unlock_extent(tree, cur, end); __do_readpage()
3067 set_extent_uptodate(tree, cur, cur + iosize - 1, __do_readpage()
3069 unlock_extent_cached(tree, cur, cur + iosize - 1, __do_readpage()
3076 if (test_range_bit(tree, cur, cur_end, __do_readpage()
3078 check_page_uptodate(tree, page); __do_readpage()
3080 unlock_extent(tree, cur, cur + iosize - 1); __do_readpage()
3091 unlock_extent(tree, cur, cur + iosize - 1); __do_readpage()
3098 ret = submit_extent_page(rw, tree, page, __do_readpage()
3111 unlock_extent(tree, cur, cur + iosize - 1); __do_readpage()
3125 static inline void __do_contiguous_readpages(struct extent_io_tree *tree, __do_contiguous_readpages() argument
3140 lock_extent(tree, start, end); __do_contiguous_readpages()
3145 unlock_extent(tree, start, end); __do_contiguous_readpages()
3151 __do_readpage(tree, pages[index], get_extent, em_cached, bio, __do_contiguous_readpages()
3157 static void __extent_readpages(struct extent_io_tree *tree, __extent_readpages() argument
3180 __do_contiguous_readpages(tree, &pages[first_index], __extent_readpages()
3192 __do_contiguous_readpages(tree, &pages[first_index], __extent_readpages()
3199 static int __extent_read_full_page(struct extent_io_tree *tree, __extent_read_full_page() argument
3212 lock_extent(tree, start, end); __extent_read_full_page()
3216 unlock_extent(tree, start, end); __extent_read_full_page()
3221 ret = __do_readpage(tree, page, get_extent, NULL, bio, mirror_num, __extent_read_full_page()
3226 int extent_read_full_page(struct extent_io_tree *tree, struct page *page, extent_read_full_page() argument
3233 ret = __extent_read_full_page(tree, page, get_extent, &bio, mirror_num, extent_read_full_page()
3240 int extent_read_full_page_nolock(struct extent_io_tree *tree, struct page *page, extent_read_full_page_nolock() argument
3247 ret = __do_readpage(tree, page, get_extent, NULL, &bio, mirror_num, extent_read_full_page_nolock()
3280 struct extent_io_tree *tree = epd->tree; writepage_delalloc() local
3288 if (epd->extent_locked || !tree->ops || !tree->ops->fill_delalloc) writepage_delalloc()
3292 nr_delalloc = find_lock_delalloc_range(inode, tree, writepage_delalloc()
3301 ret = tree->ops->fill_delalloc(inode, page, writepage_delalloc()
3371 struct extent_io_tree *tree = epd->tree; __extent_writepage_io() local
3389 if (tree->ops && tree->ops->writepage_start_hook) { __extent_writepage_io()
3390 ret = tree->ops->writepage_start_hook(page, start, __extent_writepage_io()
3414 if (tree->ops && tree->ops->writepage_end_io_hook) __extent_writepage_io()
3415 tree->ops->writepage_end_io_hook(page, start, __extent_writepage_io()
3425 if (tree->ops && tree->ops->writepage_end_io_hook) __extent_writepage_io()
3426 tree->ops->writepage_end_io_hook(page, cur, __extent_writepage_io()
3461 if (!compressed && tree->ops && __extent_writepage_io()
3462 tree->ops->writepage_end_io_hook) __extent_writepage_io()
3463 tree->ops->writepage_end_io_hook(page, cur, __extent_writepage_io()
3479 if (tree->ops && tree->ops->writepage_io_hook) { __extent_writepage_io()
3480 ret = tree->ops->writepage_io_hook(page, cur, __extent_writepage_io()
3490 set_range_writeback(tree, cur, cur + iosize - 1); __extent_writepage_io()
3497 ret = submit_extent_page(write_flags, tree, page, __extent_writepage_io()
3521 * records are inserted to lock ranges in the tree, and as dirty areas
3695 * If writeback for a btree extent that doesn't belong to a log tree set_btree_ioerr()
3714 * not be enough - we need to distinguish between log tree extents vs set_btree_ioerr()
3715 * non-log tree extents, and the next filemap_fdatawait_range() call set_btree_ioerr()
3782 struct extent_io_tree *tree = &BTRFS_I(fs_info->btree_inode)->io_tree; write_one_eb() local
3800 ret = submit_extent_page(rw, tree, p, offset >> 9, write_one_eb()
3832 struct extent_io_tree *tree = &BTRFS_I(mapping->host)->io_tree; btree_write_cache_pages() local
3837 .tree = tree, btree_write_cache_pages()
3966 static int extent_write_cache_pages(struct extent_io_tree *tree, extent_write_cache_pages() argument
4109 int extent_write_full_page(struct extent_io_tree *tree, struct page *page, extent_write_full_page() argument
4116 .tree = tree, extent_write_full_page()
4129 int extent_write_locked_range(struct extent_io_tree *tree, struct inode *inode, extent_write_locked_range() argument
4141 .tree = tree, extent_write_locked_range()
4159 if (tree->ops && tree->ops->writepage_end_io_hook) extent_write_locked_range()
4160 tree->ops->writepage_end_io_hook(page, start, extent_write_locked_range()
4173 int extent_writepages(struct extent_io_tree *tree, extent_writepages() argument
4181 .tree = tree, extent_writepages()
4188 ret = extent_write_cache_pages(tree, mapping, wbc, extent_writepages()
4195 int extent_readpages(struct extent_io_tree *tree, extent_readpages() argument
4223 __extent_readpages(tree, pagepool, nr, get_extent, &em_cached, extent_readpages()
4228 __extent_readpages(tree, pagepool, nr, get_extent, &em_cached, extent_readpages()
4243 * records from the tree
4245 int extent_invalidatepage(struct extent_io_tree *tree, extent_invalidatepage() argument
4257 lock_extent_bits(tree, start, end, 0, &cached_state); extent_invalidatepage()
4259 clear_extent_bit(tree, start, end, extent_invalidatepage()
4272 struct extent_io_tree *tree, try_release_extent_state()
4279 if (test_range_bit(tree, start, end, try_release_extent_state()
4289 ret = clear_extent_bit(tree, start, end, try_release_extent_state()
4310 struct extent_io_tree *tree, struct page *page, try_release_extent_mapping()
4334 if (!test_range_bit(tree, em->start, try_release_extent_mapping()
4339 /* once for the rb tree */ try_release_extent_mapping()
4349 return try_release_extent_state(map, tree, page, mask); try_release_extent_mapping()
4621 * removed the eb from the radix tree, so we could race btrfs_release_extent_buffer_page()
4833 * writeback flags not set) and it's still in the tree (flag find_extent_buffer()
4986 /* add one reference for the tree */ alloc_extent_buffer()
4996 * after the extent buffer is in the radix tree so alloc_extent_buffer()
5194 int read_extent_buffer_pages(struct extent_io_tree *tree, read_extent_buffer_pages() argument
5249 err = __extent_read_full_page(tree, page, read_extent_buffer_pages()
5675 * If tree ref isn't set then we know the ref on this eb is a real ref, try_release_extent_buffer()
87 __btrfs_debug_check_extent_io_range(const char *caller, struct extent_io_tree *tree, u64 start, u64 end) __btrfs_debug_check_extent_io_range() argument
1675 find_lock_delalloc_range(struct inode *inode, struct extent_io_tree *tree, struct page *locked_page, u64 *start, u64 *end, u64 max_bytes) find_lock_delalloc_range() argument
4271 try_release_extent_state(struct extent_map_tree *map, struct extent_io_tree *tree, struct page *page, gfp_t mask) try_release_extent_state() argument
4309 try_release_extent_mapping(struct extent_map_tree *map, struct extent_io_tree *tree, struct page *page, gfp_t mask) try_release_extent_mapping() argument
H A Dextent_io.h143 /* >= 0 if eb belongs to a log tree, -1 otherwise */
183 void extent_io_tree_init(struct extent_io_tree *tree,
186 struct extent_io_tree *tree, struct page *page,
189 int lock_extent(struct extent_io_tree *tree, u64 start, u64 end);
190 int lock_extent_bits(struct extent_io_tree *tree, u64 start, u64 end,
192 int unlock_extent(struct extent_io_tree *tree, u64 start, u64 end);
193 int unlock_extent_cached(struct extent_io_tree *tree, u64 start, u64 end,
195 int try_lock_extent(struct extent_io_tree *tree, u64 start, u64 end);
196 int extent_read_full_page(struct extent_io_tree *tree, struct page *page,
198 int extent_read_full_page_nolock(struct extent_io_tree *tree, struct page *page,
203 u64 count_range_bits(struct extent_io_tree *tree,
208 int test_range_bit(struct extent_io_tree *tree, u64 start, u64 end,
211 int clear_extent_bits(struct extent_io_tree *tree, u64 start, u64 end,
213 int clear_extent_bit(struct extent_io_tree *tree, u64 start, u64 end,
216 int set_extent_bits(struct extent_io_tree *tree, u64 start, u64 end,
218 int set_extent_bit(struct extent_io_tree *tree, u64 start, u64 end,
221 int set_extent_uptodate(struct extent_io_tree *tree, u64 start, u64 end,
223 int clear_extent_uptodate(struct extent_io_tree *tree, u64 start, u64 end,
225 int set_extent_new(struct extent_io_tree *tree, u64 start, u64 end,
227 int set_extent_dirty(struct extent_io_tree *tree, u64 start, u64 end,
229 int clear_extent_dirty(struct extent_io_tree *tree, u64 start, u64 end,
231 int convert_extent_bit(struct extent_io_tree *tree, u64 start, u64 end,
234 int set_extent_delalloc(struct extent_io_tree *tree, u64 start, u64 end,
236 int set_extent_defrag(struct extent_io_tree *tree, u64 start, u64 end,
238 int find_first_extent_bit(struct extent_io_tree *tree, u64 start,
241 int extent_invalidatepage(struct extent_io_tree *tree,
243 int extent_write_full_page(struct extent_io_tree *tree, struct page *page,
246 int extent_write_locked_range(struct extent_io_tree *tree, struct inode *inode,
249 int extent_writepages(struct extent_io_tree *tree,
255 int extent_readpages(struct extent_io_tree *tree,
261 int get_state_private(struct extent_io_tree *tree, u64 start, u64 *private);
276 int read_extent_buffer_pages(struct extent_io_tree *tree,
376 struct extent_io_tree *tree,
H A Dordered-data.c39 * in the tree
69 btrfs_panic(fs_info, errno, "Inconsistency in ordered tree at offset " ordered_data_tree_panic()
74 * look for a given offset in the tree, and if it can't be found return the
151 static inline struct rb_node *tree_search(struct btrfs_ordered_inode_tree *tree, tree_search() argument
154 struct rb_root *root = &tree->tree; tree_search()
159 if (tree->last) { tree_search()
160 entry = rb_entry(tree->last, struct btrfs_ordered_extent, tree_search()
163 return tree->last; tree_search()
169 tree->last = ret; tree_search()
173 /* allocate and add a new ordered_extent into the per-inode tree.
177 * extent allocation tree
181 * The tree is given a single reference on the ordered extent that was
189 struct btrfs_ordered_inode_tree *tree; __btrfs_add_ordered_extent() local
193 tree = &BTRFS_I(inode)->ordered_tree; __btrfs_add_ordered_extent()
215 /* one ref for the tree */ __btrfs_add_ordered_extent()
227 spin_lock_irq(&tree->lock); __btrfs_add_ordered_extent()
228 node = tree_insert(&tree->tree, file_offset, __btrfs_add_ordered_extent()
232 spin_unlock_irq(&tree->lock); __btrfs_add_ordered_extent()
284 struct btrfs_ordered_inode_tree *tree; btrfs_add_ordered_sum() local
286 tree = &BTRFS_I(inode)->ordered_tree; btrfs_add_ordered_sum()
287 spin_lock_irq(&tree->lock); btrfs_add_ordered_sum()
293 spin_unlock_irq(&tree->lock); btrfs_add_ordered_sum()
312 struct btrfs_ordered_inode_tree *tree; btrfs_dec_test_first_ordered_pending() local
321 tree = &BTRFS_I(inode)->ordered_tree; btrfs_dec_test_first_ordered_pending()
322 spin_lock_irqsave(&tree->lock, flags); btrfs_dec_test_first_ordered_pending()
323 node = tree_search(tree, *file_offset); btrfs_dec_test_first_ordered_pending()
365 spin_unlock_irqrestore(&tree->lock, flags); btrfs_dec_test_first_ordered_pending()
382 struct btrfs_ordered_inode_tree *tree; btrfs_dec_test_ordered_pending() local
388 tree = &BTRFS_I(inode)->ordered_tree; btrfs_dec_test_ordered_pending()
389 spin_lock_irqsave(&tree->lock, flags); btrfs_dec_test_ordered_pending()
395 node = tree_search(tree, file_offset); btrfs_dec_test_ordered_pending()
429 spin_unlock_irqrestore(&tree->lock, flags); btrfs_dec_test_ordered_pending()
439 struct btrfs_ordered_inode_tree *tree; btrfs_get_logged_extents() local
444 tree = &BTRFS_I(inode)->ordered_tree; btrfs_get_logged_extents()
445 spin_lock_irq(&tree->lock); btrfs_get_logged_extents()
446 n = __tree_search(&tree->tree, end, &prev); btrfs_get_logged_extents()
460 spin_unlock_irq(&tree->lock); btrfs_get_logged_extents()
561 * remove an ordered extent from the tree. No references are dropped
567 struct btrfs_ordered_inode_tree *tree; btrfs_remove_ordered_extent() local
571 tree = &BTRFS_I(inode)->ordered_tree; btrfs_remove_ordered_extent()
572 spin_lock_irq(&tree->lock); btrfs_remove_ordered_extent()
574 rb_erase(node, &tree->tree); btrfs_remove_ordered_extent()
575 if (tree->last == node) btrfs_remove_ordered_extent()
576 tree->last = NULL; btrfs_remove_ordered_extent()
578 spin_unlock_irq(&tree->lock); btrfs_remove_ordered_extent()
750 * when adding the new ordered extents to the ordered tree. btrfs_wait_ordered_range()
786 struct btrfs_ordered_inode_tree *tree; btrfs_lookup_ordered_extent() local
790 tree = &BTRFS_I(inode)->ordered_tree; btrfs_lookup_ordered_extent()
791 spin_lock_irq(&tree->lock); btrfs_lookup_ordered_extent()
792 node = tree_search(tree, file_offset); btrfs_lookup_ordered_extent()
802 spin_unlock_irq(&tree->lock); btrfs_lookup_ordered_extent()
813 struct btrfs_ordered_inode_tree *tree; btrfs_lookup_ordered_range() local
817 tree = &BTRFS_I(inode)->ordered_tree; btrfs_lookup_ordered_range()
818 spin_lock_irq(&tree->lock); btrfs_lookup_ordered_range()
819 node = tree_search(tree, file_offset); btrfs_lookup_ordered_range()
821 node = tree_search(tree, file_offset + len); btrfs_lookup_ordered_range()
843 spin_unlock_irq(&tree->lock); btrfs_lookup_ordered_range()
854 struct btrfs_ordered_inode_tree *tree; btrfs_lookup_first_ordered_extent() local
858 tree = &BTRFS_I(inode)->ordered_tree; btrfs_lookup_first_ordered_extent()
859 spin_lock_irq(&tree->lock); btrfs_lookup_first_ordered_extent()
860 node = tree_search(tree, file_offset); btrfs_lookup_first_ordered_extent()
867 spin_unlock_irq(&tree->lock); btrfs_lookup_first_ordered_extent()
878 struct btrfs_ordered_inode_tree *tree = &BTRFS_I(inode)->ordered_tree; btrfs_ordered_update_i_size() local
887 spin_lock_irq(&tree->lock); btrfs_ordered_update_i_size()
929 prev = tree_search(tree, offset); btrfs_ordered_update_i_size()
987 spin_unlock_irq(&tree->lock); btrfs_ordered_update_i_size()
1001 struct btrfs_ordered_inode_tree *tree = &BTRFS_I(inode)->ordered_tree; btrfs_find_ordered_sum() local
1011 spin_lock_irq(&tree->lock); btrfs_find_ordered_sum()
1030 spin_unlock_irq(&tree->lock); btrfs_find_ordered_sum()
H A Drelocation.c44 * present a tree block in the backref cache
51 /* objectid of tree block owner, can be not uptodate */
59 /* NULL if this node is not tree root */
63 /* level of tree block */
65 /* is the block in non-reference counted tree */
100 /* red black tree of all backref nodes in the cache */
124 * map address of tree root to tree
138 * present a tree block to process
160 /* extent tree */
170 /* tree blocks have been processed */
172 /* map start of tree root to corresponding reloc tree */
178 /* size of relocated tree nodes */
201 static void mapping_tree_init(struct mapping_tree *tree) mapping_tree_init() argument
203 tree->rb_root = RB_ROOT; mapping_tree_init()
204 spin_lock_init(&tree->lock); mapping_tree_init()
344 * walk up backref nodes until reach node presents tree root
408 static void drop_backref_node(struct backref_cache *tree, drop_backref_node() argument
417 rb_erase(&node->rb_node, &tree->rb_root); drop_backref_node()
418 free_backref_node(tree, node); drop_backref_node()
492 * lookup. transaction commit changes the extent tree. update_backref_cache()
542 * if there is reloc tree and it was created in previous should_ignore_root()
543 * transaction backref lookup can find the reloc tree, should_ignore_root()
544 * so backref node for the fs tree root is useless for should_ignore_root()
550 * find reloc tree by address of tree root
665 * build backref tree for a given tree block. root of the backref tree
666 * corresponds the tree block, leaves of the backref tree correspond
667 * roots of b-trees that reference the tree block.
672 * when tree root is reached or backrefs for the block is cached.
895 /* tree root */
908 * searching the tree to find upper level blocks
974 * while walking up a tree as we will catch
1098 * process useless backref nodes. backref nodes for tree leaves
1100 * tree blocks are left in the cache to avoid unnecessary backref
1184 * corresponds to root of source tree
1273 * helper to add 'address of tree root -> reloc tree' mapping
1295 "tree", node->bytenr); __add_reloc_root()
1305 * helper to delete the 'address of tree root -> reloc tree'
1334 * helper to update the 'address of tree root -> reloc tree'
1395 * the source tree is a reloc tree, all tree blocks create_reloc_root()
1417 * receive data into a relocation tree. create_reloc_root()
1438 * create reloc tree for a given fs tree. reloc tree is just a
1439 * snapshot of the fs tree with special root objectid.
1476 * update root item of reloc tree
1622 * update file extent items in the tree leaf to point to
1672 * if we are modifying block in fs tree, wait for readpage replace_file_extents()
1752 * try to replace tree blocks in fs tree with the new blocks
1753 * in reloc tree. tree blocks haven't been modified since the
1754 * reloc tree was create can be replaced.
1887 * swap blocks in fs tree and reloc tree. replace_path()
1931 * helper to find next relocated block in reloc tree
1968 * walk down reloc tree to find relocated block of lowest level
2107 * merge the relocated tree blocks in reloc tree with corresponding
2108 * fs tree.
2232 * handle the case only one block in the fs tree need to be merge_reloc_root()
2233 * relocated and the block is tree root. merge_reloc_root()
2396 * created the relocation tree. merge_reloc_roots()
2516 * select a tree root for relocation. return NULL if the block
2518 * case. return a tree root pointer if the block isn't reference
2519 * counted. return -ENOENT if the block is root of reloc tree.
2538 /* no other choice for non-references counted tree */ select_one_root()
2629 * relocate a block tree, and then update pointers in upper level
2891 * helper function to relocate a tree block
3272 * helper to add a tree block to the list.
3344 * helper to add tree blocks for backref of type BTRFS_SHARED_DATA_REF_KEY
3478 * helper to add tree blocks for backref of type BTRFS_EXTENT_DATA_REF_KEY
3479 * this function scans fs tree to find blocks reference the data extent
3550 * the references in tree blocks that use full backrefs find_data_references()
3647 * helper to find all tree blocks that reference a given data extent
3889 * extent tree is not a ref_cow tree and has no reloc_root to prepare_to_relocate()
4011 * if we fail to relocate tree blocks, force to update relocate_block_group()
4124 * the inode is in data relocation tree and its link count is 0
4321 * this is important for keeping the sharing of tree blocks
4464 /* cleanup orphan inode in data relocation tree */ btrfs_recover_relocation()
4586 * requried for relocating tree blocks in the snapshot
4607 * used by merging a reloc tree is twice the size of btrfs_reloc_pre_snapshot()
4608 * relocated tree nodes in the worst case. half for cowing btrfs_reloc_pre_snapshot()
4609 * the reloc tree, half for cowing the fs tree. the space btrfs_reloc_pre_snapshot()
4610 * used by cowing the reloc tree will be freed after the btrfs_reloc_pre_snapshot()
4611 * tree is dropped. if we create snapshot, cowing the fs btrfs_reloc_pre_snapshot()
4612 * tree may use more space than it frees. so we need btrfs_reloc_pre_snapshot()
H A Ddelayed-ref.h22 #define BTRFS_ADD_DELAYED_REF 1 /* add one backref to the tree */
23 #define BTRFS_DROP_DELAYED_REF 2 /* delete one backref from the tree */
101 * The actual extent isn't inserted into the extent allocation tree
107 * inserted into the extent allocation tree. In this case
143 /* total number of head nodes in tree */
152 * set when the tree is flushing before a transaction commit,
H A Dtree-log.c23 #include "tree-log.h"
26 #include "print-tree.h"
78 * directory tree. The inode link count fixup code takes care of the
83 * stages for the tree walking. The first
112 * tree logging is a special write ahead log used to make sure that
113 * fsyncs and O_SYNCs can happen without doing full tree commits.
115 * Full tree commits are expensive because they require commonly
117 * extent tree an 4x-6x higher write load than ext3.
119 * Instead of doing a tree commit on every fsync, we use the
122 * a special tree (one per subvolume root), that tree is written to disk
125 * After a crash, items are copied out of the log-tree back into the
126 * subvolume tree. Any file data extents found are recorded in the extent
127 * allocation tree, and the log-tree freed.
129 * The log tree is read three times, once to pin down all the extents it is
130 * using in ram and once, once to create all the inodes logged in the tree
135 * start a sub transaction and setup the log tree
136 * this increments the log tree writer count to make the people
137 * syncing the tree wait for us to finish
235 * indicate we're done making changes to the log tree
250 * processing the log tree. The stage field tells us which part
251 * of the log tree processing we are currently doing. The others
256 * at transaction commit time while freeing a log tree
261 * while flushing the log tree to disk during a sync
266 * while flushing the log tree to disk for a sync
285 * tree. Note the extent_buffer might not be up to date when it is
328 * Item overwrite used by replay and tree logging. eb, slot and key all refer
331 * root is the tree we are copying into, and path is a scratch
335 * If the key is already in the destination tree the existing item is
362 /* look for the key in the destination tree */ overwrite_item()
399 * us from cowing blocks in the destination tree and doing overwrite_item()
455 /* try to insert the key into the destination tree */ overwrite_item()
478 * was logged as zero. This is done when the tree logging code overwrite_item()
483 * state of the tree found in the subvolume, and i_size is modified overwrite_item()
502 * tree, otherwise we would be throwing valid data away. overwrite_item()
576 * extents in the log tree have not been allocated out of the extent
577 * tree yet. So, this completes the allocation, taking a reference
579 * if it isn't in the extent allocation tree yet.
695 * allocation tree? If so, just add a reference replay_one_extent()
709 * allocation tree replay_one_extent()
857 * helper function to check a log tree for a named back reference in
1000 * NOTE: we have searched root tree and checked the __add_inode_ref()
1144 * replay one inode back reference item found in the log tree.
1145 * eb, slot and key refer to the buffer and key found in the log tree.
1610 * fix up tree.
1822 /* check the next slot in the tree to see if it is a valid item */ find_dir_range()
2021 /* Doesn't exist in log tree, so delete it. */ replay_xattr_deletes()
2167 * the process_func used to replay items from the log tree. This
2444 * drop the reference count on the tree rooted at 'snap'. This traverses
2445 * the tree freeing any blocks that have a ref count of zero after being
2520 * in the tree of log roots
2612 * btrfs_sync_log does sends a given tree log down to the disk and
2652 /* wait for previous tree log sync to complete */ btrfs_sync_log()
2703 * IO has been started, blocks of the log tree have WRITTEN flag set btrfs_sync_log()
2780 * now that we've moved on to the tree of log tree roots, btrfs_sync_log()
2899 * We may have short-circuited the log tree with the full commit logic free_log_tree()
2911 * free all the extents used by the tree log. This should be called
3128 * directory. This also creates the range items in the log tree required
3314 * key in the range logged that is not present in the log tree, then it means
3398 * found the last guy with the objectid in this tree. drop_objectid_items()
3619 * log tree while trying to change the log tree. copy_items()
4032 struct extent_map_tree *tree = &BTRFS_I(inode)->extent_tree; btrfs_log_changed_extents() local
4039 write_lock(&tree->lock); btrfs_log_changed_extents()
4042 list_for_each_entry_safe(em, n, &tree->modified_extents, list) { btrfs_log_changed_extents()
4052 list_del_init(&tree->modified_extents); btrfs_log_changed_extents()
4079 clear_em_logging(tree, em); btrfs_log_changed_extents()
4084 write_unlock(&tree->lock); btrfs_log_changed_extents()
4088 write_lock(&tree->lock); btrfs_log_changed_extents()
4089 clear_em_logging(tree, em); btrfs_log_changed_extents()
4093 write_unlock(&tree->lock); btrfs_log_changed_extents()
4129 * in the log tree and exists in the fs/subvol tree, we delete it. This is
4220 * file correspond to a hole. The presence of explicit holes in a log tree is
4222 * fs/subvol tree.
4226 * lookup for extents from the fs/subvol tree only. In the fast path case, we
4228 * insert a corresponding extent representing a hole in the log tree.
4428 /* log a single inode in the tree log.
4429 * At least one parent directory for this inode must exist in the tree
4433 * to the log tree. An extra reference is taken on any extents in this
4435 * blocks that have been removed from the tree.
4727 * ordered tree. We want the application/user space to know an btrfs_log_inode()
4730 * without writing to the log tree and the fsync must report the btrfs_log_inode()
4756 * tree yet, and need to let the next fast fsync (one which btrfs_log_inode()
4910 * BTRFS_DIR_INDEX_KEY are added to fs/subvol tree and the logged inode item
4916 * name is added to the fs/subvol tree with both the dir_item and dir_index
4920 * item of the fs/subvol tree (see overwrite_item()).
5245 "recovering log root tree."); btrfs_recover_log_trees()
5259 "Couldn't find tree log root."); btrfs_recover_log_trees()
5277 "Couldn't read tree log root."); btrfs_recover_log_trees()
5292 "for tree log recovery."); btrfs_recover_log_trees()
H A Dctree.c25 #include "print-tree.h"
139 * safely gets a reference on the root node of a tree. A lock
141 * at the root of the tree. See btrfs_lock_root_node for the
145 * it won't disappear. It may stop being the root of the tree
173 * tree until you end up with a lock on the root. A locked buffer
192 * tree until you end up with a lock on the root. A locked buffer
222 /* Want the extent tree to be the last on the list */ add_root_to_dirty_list()
234 * used by snapshot creation to make a copy of a root for a tree with
356 * Pull a new tree mod seq number for our operation.
364 * This adds a new blocker to the tree mod log's blocker list if the @elem
366 * to record tree modifications, it should ensure to set elem->seq to zero
368 * Returns a fresh, unused tree log modification sequence number, even if no new
421 * sequence number can be removed from the tree. btrfs_put_tree_mod_seq()
483 * this until all tree mod log insertions are recorded in the rb tree and then
952 * check if the tree block can be shared by multiple trees
958 * Tree blocks not in refernece counted trees and tree roots btrfs_block_can_be_shared()
960 * snapshot and the block was not allocated by tree relocation, btrfs_block_can_be_shared()
992 * Always use full backrefs for extent pointers in tree block update_ref_for_cow()
993 * allocated by tree relocation. update_ref_for_cow()
995 * If a shared tree block is no longer referenced by its owner update_ref_for_cow()
996 * tree (btrfs_header_owner(buf) == root->root_key.objectid), update_ref_for_cow()
997 * use full backrefs for extent pointers in tree block. update_ref_for_cow()
999 * If a tree block is been relocating update_ref_for_cow()
1001 * use full backrefs for extent pointers in tree block. update_ref_for_cow()
1002 * The reason for this is some operations (such as drop tree) update_ref_for_cow()
1241 * if there are no tree operation for the oldest root, we simply __tree_mod_log_oldest_root()
1328 * have a root-replace operation for B, a tree block __tree_mod_log_rewind()
1445 "failed to read tree block %llu from get_old_root", logical); get_old_root()
1511 * 2) this block does not belong to TREE_RELOC tree; should_cow_block()
2018 * tree during a delete. A deletion from lower in the tree balance_level()
2348 * when we walk down the tree, it is usually safe to unlock the higher layers
2349 * in the tree. The exceptions are when our path goes through slot 0, because
2350 * operations on the tree might require changing key pointers higher up in the
2351 * tree.
2355 * walking through the tree, and selecting the next slot in the higher block.
2357 * lowest_unlock sets the lowest level in the tree we're allowed to unlock. so
2410 * more updates to be done higher up in the tree.
2652 * look for key in the tree. path is filled in with nodes along the way
2661 * tree. if ins_len < 0, nodes will be merged as we walk down the tree (if
2690 * two as we update tree pointers Make sure we keep write btrfs_search_slot()
2801 * the tree, there is no way to for the items in b to change. btrfs_search_slot()
2934 * Like btrfs_search_slot, this looks for a key in the given tree. It uses the
2935 * current state of the tree together with the operations recorded in the tree
2936 * modification log to search for the key in a previous version of this tree, as
2976 * the tree, there is no way to for the items in b to change. btrfs_search_old_slot()
3053 * It returns 0 if any item is found, 1 if none is found (tree empty), and
3121 * adjust the pointers going up the tree, starting at level
3182 * tree.
3254 * tree.
3319 * helper function to insert a new root level in the tree.
3459 * tree mod log: We don't log_removal old root in split_node()
3463 * tree lock on the buffer, which is why we cannot race with split_node()
4474 * a tree block with room for one extra struct btrfs_item
4497 * It guarantees both items live in the same tree leaf and the new item
4794 * Given a key and some data, insert items into the tree.
4795 * This does all the path init required, making room in the tree if needed.
4828 * Given a key and some data, insert an item into the tree.
4829 * This does all the path init required, making room in the tree if needed.
4857 * the tree should have been previously balanced so the deletion does not
4930 * the leaf, remove it from the tree
5044 * search the tree again to find a leaf with lesser keys
5079 * We might have had an item with the previous key in the tree right btrfs_prev_leaf()
5082 * were holding due to a tree balance. Alternatively, an item with the btrfs_prev_leaf()
5094 * A helper function to walk down the tree starting at min_key, and looking
5096 * This is used by the btree defrag code, and tree logging
5106 * of the tree.
5113 * was nothing in the tree that matched the search criteria.
5314 * If shared tree blocks are encountered, whole subtrees are skipped, making
5375 * If left < right treat left item as new, advance left tree btrfs_compare_trees()
5377 * If left > right treat right item as deleted, advance right tree btrfs_compare_trees()
5383 * If left < right advance left tree and repeat btrfs_compare_trees()
5384 * If left > right advance right tree and repeat btrfs_compare_trees()
5390 * If tree levels are different btrfs_compare_trees()
5391 * Advance the tree that needs it and repeat btrfs_compare_trees()
5393 * Advancing a tree means: btrfs_compare_trees()
5399 * If we are not at level 0 and not on shared tree blocks, go one btrfs_compare_trees()
5402 * If we are not at level 0 and on shared tree blocks, go one slot to btrfs_compare_trees()
5570 * tree based on the current path and the min_trans parameters.
5573 * and 1 is returned if there are no higher keys in the tree
5644 * search the tree again to find a leaf with greater keys
5827 * this uses btrfs_prev_leaf to walk backwards in the tree, and keeps
5870 * search in extent tree to find a previous Metadata/Data extent item with
H A Dordered-data.h25 struct rb_root tree; member in struct:btrfs_ordered_inode_tree
46 * It is used to make sure metadata is inserted into the tree only once
51 * IO is done and any metadata is inserted into the tree.
55 #define BTRFS_ORDERED_COMPLETE 1 /* set when removed from the tree */
160 t->tree = RB_ROOT; btrfs_ordered_inode_tree_init()
/linux-4.1.27/net/sched/
H A Dematch.c166 static inline struct tcf_ematch *tcf_em_get_match(struct tcf_ematch_tree *tree, tcf_em_get_match() argument
169 return &tree->matches[index]; tcf_em_get_match()
289 * tcf_em_tree_validate - validate ematch config TLV and build ematch tree
292 * @nla: ematch tree configuration TLV
293 * @tree: destination ematch tree variable to store the resulting
294 * ematch tree.
297 * ematch tree in @tree. The resulting tree must later be copied into
299 * provide the ematch tree variable of the private classifier data directly,
305 struct tcf_ematch_tree *tree) tcf_em_tree_validate()
313 memset(tree, 0, sizeof(*tree)); tcf_em_tree_validate()
329 memcpy(&tree->hdr, tree_hdr, sizeof(*tree_hdr)); tcf_em_tree_validate()
335 tree->matches = kzalloc(matches_len, GFP_KERNEL); tcf_em_tree_validate()
336 if (tree->matches == NULL) tcf_em_tree_validate()
360 em = tcf_em_get_match(tree, idx); tcf_em_tree_validate()
384 tcf_em_tree_destroy(tree); tcf_em_tree_validate()
390 * tcf_em_tree_destroy - destroy an ematch tree
393 * @tree: ematch tree to be deleted
395 * This functions destroys an ematch tree previously created by
397 * the ematch tree is not in use before calling this function.
399 void tcf_em_tree_destroy(struct tcf_ematch_tree *tree) tcf_em_tree_destroy() argument
403 if (tree->matches == NULL) tcf_em_tree_destroy()
406 for (i = 0; i < tree->hdr.nmatches; i++) { tcf_em_tree_destroy()
407 struct tcf_ematch *em = tcf_em_get_match(tree, i); tcf_em_tree_destroy()
418 tree->hdr.nmatches = 0; tcf_em_tree_destroy()
419 kfree(tree->matches); tcf_em_tree_destroy()
420 tree->matches = NULL; tcf_em_tree_destroy()
425 * tcf_em_tree_dump - dump ematch tree into a rtnl message
428 * @t: ematch tree to be dumped
429 * @tlv: TLV type to be used to encapsulate the tree
431 * This function dumps a ematch tree into a rtnl message. It is valid to
432 * call this function while the ematch tree is in use.
436 int tcf_em_tree_dump(struct sk_buff *skb, struct tcf_ematch_tree *tree, int tlv) tcf_em_tree_dump() argument
447 if (nla_put(skb, TCA_EMATCH_TREE_HDR, sizeof(tree->hdr), &tree->hdr)) tcf_em_tree_dump()
455 for (i = 0; i < tree->hdr.nmatches; i++) { tcf_em_tree_dump()
457 struct tcf_ematch *em = tcf_em_get_match(tree, i); tcf_em_tree_dump()
499 int __tcf_em_tree_match(struct sk_buff *skb, struct tcf_ematch_tree *tree, __tcf_em_tree_match() argument
507 while (match_idx < tree->hdr.nmatches) { __tcf_em_tree_match()
508 cur_match = tcf_em_get_match(tree, match_idx); __tcf_em_tree_match()
530 cur_match = tcf_em_get_match(tree, match_idx); __tcf_em_tree_match()
304 tcf_em_tree_validate(struct tcf_proto *tp, struct nlattr *nla, struct tcf_ematch_tree *tree) tcf_em_tree_validate() argument
/linux-4.1.27/mm/
H A Dzswap.c167 * rbnode - links the entry into red-black tree for the appropriate swap type
174 * offset - the swap offset for the entry. Index into the red-black tree.
192 * The tree lock in the zswap_tree struct protects a few things:
194 * - the refcount field of each entry in the tree
302 /* caller must hold the tree lock */ zswap_entry_get()
308 /* caller must hold the tree lock
309 * remove from the tree and free it, if nobody reference the entry
311 static void zswap_entry_put(struct zswap_tree *tree, zswap_entry_put() argument
318 zswap_rb_erase(&tree->rbroot, entry); zswap_entry_put()
323 /* caller must hold the tree lock */ zswap_entry_find_get()
492 /* May fail (-ENOMEM) if radix-tree node allocation failed. */ zswap_get_swap_cache_page()
536 struct zswap_tree *tree; zswap_writeback_entry() local
551 tree = zswap_trees[swp_type(swpentry)]; zswap_writeback_entry()
555 spin_lock(&tree->lock); zswap_writeback_entry()
556 entry = zswap_entry_find_get(&tree->rbroot, offset); zswap_writeback_entry()
559 spin_unlock(&tree->lock); zswap_writeback_entry()
562 spin_unlock(&tree->lock); zswap_writeback_entry()
602 spin_lock(&tree->lock); zswap_writeback_entry()
604 zswap_entry_put(tree, entry); zswap_writeback_entry()
608 * (1) refcount is 1(normal case), entry is valid and on the tree zswap_writeback_entry()
609 * (2) refcount is 0, entry is freed and not on the tree zswap_writeback_entry()
611 * search the tree and free the entry if find entry zswap_writeback_entry()
613 if (entry == zswap_rb_search(&tree->rbroot, offset)) zswap_writeback_entry()
614 zswap_entry_put(tree, entry); zswap_writeback_entry()
615 spin_unlock(&tree->lock); zswap_writeback_entry()
627 spin_lock(&tree->lock); zswap_writeback_entry()
628 zswap_entry_put(tree, entry); zswap_writeback_entry()
629 spin_unlock(&tree->lock); zswap_writeback_entry()
642 struct zswap_tree *tree = zswap_trees[type]; zswap_frontswap_store() local
651 if (!tree) { zswap_frontswap_store()
709 spin_lock(&tree->lock); zswap_frontswap_store()
711 ret = zswap_rb_insert(&tree->rbroot, entry, &dupentry); zswap_frontswap_store()
715 zswap_rb_erase(&tree->rbroot, dupentry); zswap_frontswap_store()
716 zswap_entry_put(tree, dupentry); zswap_frontswap_store()
719 spin_unlock(&tree->lock); zswap_frontswap_store()
741 struct zswap_tree *tree = zswap_trees[type]; zswap_frontswap_load() local
748 spin_lock(&tree->lock); zswap_frontswap_load()
749 entry = zswap_entry_find_get(&tree->rbroot, offset); zswap_frontswap_load()
752 spin_unlock(&tree->lock); zswap_frontswap_load()
755 spin_unlock(&tree->lock); zswap_frontswap_load()
768 spin_lock(&tree->lock); zswap_frontswap_load()
769 zswap_entry_put(tree, entry); zswap_frontswap_load()
770 spin_unlock(&tree->lock); zswap_frontswap_load()
778 struct zswap_tree *tree = zswap_trees[type]; zswap_frontswap_invalidate_page() local
782 spin_lock(&tree->lock); zswap_frontswap_invalidate_page()
783 entry = zswap_rb_search(&tree->rbroot, offset); zswap_frontswap_invalidate_page()
786 spin_unlock(&tree->lock); zswap_frontswap_invalidate_page()
791 zswap_rb_erase(&tree->rbroot, entry); zswap_frontswap_invalidate_page()
794 zswap_entry_put(tree, entry); zswap_frontswap_invalidate_page()
796 spin_unlock(&tree->lock); zswap_frontswap_invalidate_page()
802 struct zswap_tree *tree = zswap_trees[type]; zswap_frontswap_invalidate_area() local
805 if (!tree) zswap_frontswap_invalidate_area()
808 /* walk the tree and free everything */ zswap_frontswap_invalidate_area()
809 spin_lock(&tree->lock); zswap_frontswap_invalidate_area()
810 rbtree_postorder_for_each_entry_safe(entry, n, &tree->rbroot, rbnode) zswap_frontswap_invalidate_area()
812 tree->rbroot = RB_ROOT; zswap_frontswap_invalidate_area()
813 spin_unlock(&tree->lock); zswap_frontswap_invalidate_area()
814 kfree(tree); zswap_frontswap_invalidate_area()
824 struct zswap_tree *tree; zswap_frontswap_init() local
826 tree = kzalloc(sizeof(struct zswap_tree), GFP_KERNEL); zswap_frontswap_init()
827 if (!tree) { zswap_frontswap_init()
832 tree->rbroot = RB_ROOT; zswap_frontswap_init()
833 spin_lock_init(&tree->lock); zswap_frontswap_init()
834 zswap_trees[type] = tree; zswap_frontswap_init()
H A Dksm.c60 * insert the pages into a normal sorted tree and expect it to find anything.
61 * Therefore KSM uses two data structures - the stable and the unstable tree.
63 * The stable tree holds pointers to all the merged pages (ksm pages), sorted
65 * this tree is fully assured to be working (except when pages are unmapped),
66 * and therefore this tree is called the stable tree.
68 * In addition to the stable tree, KSM uses a second data structure called the
69 * unstable tree: this tree holds pointers to pages which have been found to
70 * be "unchanged for a period of time". The unstable tree sorts these pages
72 * upon the unstable tree to work correctly - the unstable tree is liable to
77 * 1) The unstable tree is flushed every time KSM completes scanning all
78 * memory areas, and then the tree is rebuilt again from the beginning.
79 * 2) KSM will only insert into the unstable tree, pages whose hash value
81 * 3) The unstable tree is a RedBlack Tree - so its balancing is based on the
83 * the tree gets "corrupted" it won't get out of balance, so scanning time
86 * 4) KSM never flushes the stable tree, which means that even if it were to
87 * take 10 attempts to find a page in the unstable tree, once it is found,
88 * it is secured in the stable tree. (When we scan a new page, we first
89 * compare it against the stable tree, and then against the unstable tree.)
127 * @node: rb node of this ksm page in the stable tree
129 * @list: linked into migrate_nodes, pending placement in the proper node tree
132 * @nid: NUMA node id of stable tree in which linked (may not match kpfn)
136 struct rb_node node; /* when node of stable tree */
152 * @anon_vma: pointer to anon_vma for this mm,address, when in stable tree
153 * @nid: NUMA node id of unstable tree in which linked (may not match page)
157 * @node: rb node of this rmap_item in the unstable tree
158 * @head: pointer to stable_node heading this list in the stable tree
166 int nid; /* when node of unstable tree */
173 struct rb_node node; /* when node of unstable tree */
174 struct { /* when listed from stable tree */
181 #define SEQNR_MASK 0x0ff /* low bits of unstable tree seqnr */
182 #define UNSTABLE_FLAG 0x100 /* is a node of the unstable tree */
183 #define STABLE_FLAG 0x200 /* is listed from the stable tree */
185 /* The stable and unstable tree heads */
191 /* Recently migrated nodes of stable tree, pending proper placement */
208 /* The number of nodes in the stable tree */
214 /* The number of nodes in the unstable tree */
403 * than we're counting as nodes in the stable tree; but ksm_do_scan break_ksm()
485 * This helper is used for getting right index into array of tree roots.
488 * every node has its own stable and unstable tree.
522 * remove the stale node from the stable tree and return NULL.
610 * Removing rmap_item from stable or unstable tree.
611 * This function will clean the information from the stable/unstable tree.
669 * Though it's very tempting to unmerge rmap_items from stable tree rather
671 * that - an rmap_item is assigned to the stable tree after inserting ksm
1143 * stable_tree_search - search for page inside the stable tree
1145 * This function checks if there is a page inside the stable tree
1148 * This function returns the stable tree node of identical content if found,
1210 * There is now a place for page_node, but the tree may stable_tree_search()
1245 * stable_tree_insert - insert stable tree node pointing to new ksm page
1246 * into the stable tree.
1248 * This function returns the stable tree node just allocated on success,
1309 * else insert rmap_item into the unstable tree.
1311 * This function searches for a page in the unstable tree identical to the
1313 * tree, we insert rmap_item as a new object into the unstable tree.
1368 * tree next time: only merge with it when across_nodes. unstable_tree_search_insert()
1390 * rmap_items hanging off a given node of the stable tree, all sharing
1407 * cmp_and_merge_page - first see if page can be merged into the stable tree;
1409 * be inserted into the unstable tree, or merged with a page already there and
1410 * both transferred to the stable tree.
1438 /* We first start with searching the page inside the stable tree */ cmp_and_merge_page()
1452 * add its rmap_item to the stable tree. cmp_and_merge_page()
1465 * don't want to insert it in the unstable tree, and we don't want cmp_and_merge_page()
1483 * node in the stable tree and add both rmap_items. cmp_and_merge_page()
1494 * If we fail to insert the page into the stable tree, cmp_and_merge_page()
1496 * to a ksm page left outside the stable tree, cmp_and_merge_page()
1904 * to that page's node of the stable tree. rmap_walk_ksm()
2035 * it is unsafe for them to touch the stable tree at this time. ksm_memory_callback()
2048 * pages which have been offlined: prune those from the tree, ksm_memory_callback()
2220 /* Stable tree is empty but not the unstable */ merge_across_nodes_store()
H A Dinterval_tree.c2 * mm/interval_tree.c - interval tree for mapping->i_mmap
28 /* Insert node immediately after prev in the interval tree */ vma_interval_tree_insert_after()
/linux-4.1.27/scripts/tracing/
H A Ddraw_functrace.py9 The resulted trace is processed into a tree to produce a more human
10 view of the call stack by drawing textual but hierarchical tree of
28 """ This class provides a tree representation of the functions
46 into the tree at the appropriate place.
59 tree = self
60 while tree != CallTree.ROOT and tree._func != func:
61 tree = tree._parent
62 if tree == CallTree.ROOT:
65 return tree
114 tree = CallTree.ROOT
123 tree = tree.getParent(caller)
124 tree = tree.calls(callee, calltime)
/linux-4.1.27/sound/hda/
H A Dhdac_sysfs.c70 * Widget tree sysfs
72 * This is a tree showing the attributes of each widget. It appears like
313 struct hdac_widget_tree *tree = codec->widgets; widget_tree_free() local
316 if (!tree) widget_tree_free()
318 free_widget_node(tree->afg, &widget_afg_group); widget_tree_free()
319 if (tree->nodes) { widget_tree_free()
320 for (p = tree->nodes; *p; p++) widget_tree_free()
322 kfree(tree->nodes); widget_tree_free()
324 if (tree->root) widget_tree_free()
325 kobject_put(tree->root); widget_tree_free()
326 kfree(tree); widget_tree_free()
355 struct hdac_widget_tree *tree; widget_tree_create() local
359 tree = codec->widgets = kzalloc(sizeof(*tree), GFP_KERNEL); widget_tree_create()
360 if (!tree) widget_tree_create()
363 tree->root = kobject_create_and_add("widgets", &codec->dev.kobj); widget_tree_create()
364 if (!tree->root) widget_tree_create()
367 tree->nodes = kcalloc(codec->num_nodes + 1, sizeof(*tree->nodes), widget_tree_create()
369 if (!tree->nodes) widget_tree_create()
373 err = add_widget_node(tree->root, nid, &widget_node_group, widget_tree_create()
374 &tree->nodes[i]); widget_tree_create()
380 err = add_widget_node(tree->root, codec->afg, widget_tree_create()
381 &widget_afg_group, &tree->afg); widget_tree_create()
386 kobject_uevent(tree->root, KOBJ_CHANGE); widget_tree_create()
/linux-4.1.27/fs/ext4/
H A Dextents_status.c10 * Ext4 extents status tree core functions.
21 * will introduce a new structure called io tree to track all extent
24 * Delay extent tree is the first step to achieve this goal. It is
26 * extent tree, whose goal is only track delayed extents in memory to
29 * delay extent tree at the first commit. But for better understand
30 * what it does, it has been rename to extent status tree.
34 * tracked in the tree. It maintains the delayed extent when a delayed
40 * status tree and future works.
43 * In this step all extent status are tracked by extent status tree.
44 * Thus, we can first try to lookup a block mapping in this tree before
45 * finding it in extent tree. Hence, single extent cache can be removed
46 * because extent status tree can do a better job. Extents in status
47 * tree are loaded on-demand. Therefore, the extent status tree may not
49 * to reclaim memory from extent status tree because fragmented extent
50 * tree will make status tree cost too much memory. written/unwritten/-
51 * hole extents in the tree will be reclaimed by this shrinker when we
57 * Extent status tree implementation for ext4.
61 * Extent status tree tracks all extent status.
63 * 1. Why we need to implement extent status tree?
65 * Without extent status tree, ext4 identifies a delayed extent by looking
72 * Let us have a look at how they do without extent status tree.
89 * With extent status tree implementation, FIEMAP, SEEK_HOLE/DATA,
92 * not by searching the extent tree.
96 * 2. Ext4 extent status tree impelmentation
100 * physically. Unlike extent in extent tree, this extent in ext4 is
105 * -- extent status tree
106 * Every inode has an extent status tree and all allocation blocks
107 * are added to the tree with different status. The extent in the
108 * tree are ordered by logical block no.
110 * -- operations on a extent status tree
111 * There are three important operations on a delayed extent tree: find
114 * -- race on a extent status tree
115 * Extent status tree is protected by inode->i_es_lock.
118 * Fragmented extent tree will make extent status tree cost too much
120 * the tree under a heavy memory pressure.
168 void ext4_es_init_tree(struct ext4_es_tree *tree) ext4_es_init_tree() argument
170 tree->root = RB_ROOT; ext4_es_init_tree()
171 tree->cache_es = NULL; ext4_es_init_tree()
177 struct ext4_es_tree *tree; ext4_es_print_tree() local
181 tree = &EXT4_I(inode)->i_es_tree; ext4_es_print_tree()
182 node = rb_first(&tree->root); ext4_es_print_tree()
204 * search through the tree for an delayed extent with a given offset. If
248 struct ext4_es_tree *tree = NULL; ext4_es_find_delayed_extent_range() local
257 tree = &EXT4_I(inode)->i_es_tree; ext4_es_find_delayed_extent_range()
261 if (tree->cache_es) { ext4_es_find_delayed_extent_range()
262 es1 = tree->cache_es; ext4_es_find_delayed_extent_range()
271 es1 = __es_tree_search(&tree->root, lblk); ext4_es_find_delayed_extent_range()
287 tree->cache_es = es1; ext4_es_find_delayed_extent_range()
415 struct ext4_es_tree *tree = &EXT4_I(inode)->i_es_tree; ext4_es_try_to_merge_left() local
428 rb_erase(&es->rb_node, &tree->root); ext4_es_try_to_merge_left()
439 struct ext4_es_tree *tree = &EXT4_I(inode)->i_es_tree; ext4_es_try_to_merge_right() local
452 rb_erase(node, &tree->root); ext4_es_try_to_merge_right()
558 * access direct/indirect tree from outside. It is too dirty to define ext4_es_insert_extent_ind_check()
634 struct ext4_es_tree *tree = &EXT4_I(inode)->i_es_tree; __es_insert_extent() local
635 struct rb_node **p = &tree->root.rb_node; __es_insert_extent()
677 rb_insert_color(&es->rb_node, &tree->root); __es_insert_extent()
680 tree->cache_es = es; __es_insert_extent()
686 * status tree.
698 es_debug("add [%u/%u) %llu %x to extent status tree of inode %lu\n", ext4_es_insert_extent()
743 * tree if and only if there isn't information about the range in
773 * ext4_es_lookup_extent() looks up an extent in extent status tree.
782 struct ext4_es_tree *tree; ext4_es_lookup_extent() local
791 tree = &EXT4_I(inode)->i_es_tree; ext4_es_lookup_extent()
796 if (tree->cache_es) { ext4_es_lookup_extent()
797 es1 = tree->cache_es; ext4_es_lookup_extent()
806 node = tree->root.rb_node; ext4_es_lookup_extent()
842 struct ext4_es_tree *tree = &EXT4_I(inode)->i_es_tree; __es_remove_extent() local
852 es = __es_tree_search(&tree->root, lblk); __es_remove_extent()
859 tree->cache_es = NULL; __es_remove_extent()
914 rb_erase(&es->rb_node, &tree->root); __es_remove_extent()
940 * ext4_es_remove_extent() removes a space from a extent status tree.
951 es_debug("remove [%u/%u) from extent status tree of inode %lu\n", ext4_es_remove_extent()
1239 * Return 0 if we hit end of tree / interval, 1 if we exhausted nr_to_scan.
1247 struct ext4_es_tree *tree = &ei->i_es_tree; es_do_reclaim_extents() local
1251 es = __es_tree_search(&tree->root, ei->i_es_shrink_lblk); es_do_reclaim_extents()
1264 * We can't reclaim delayed extent from status tree because es_do_reclaim_extents()
1274 rb_erase(&es->rb_node, &tree->root); es_do_reclaim_extents()
/linux-4.1.27/drivers/sh/intc/
H A Dvirq.c15 #include <linux/radix-tree.h>
31 * Tags for the radix tree
65 * fast-path out if the tree is untagged, so there is no intc_irq_lookup()
66 * need to explicitly test the root tree. intc_irq_lookup()
68 tagged = radix_tree_tag_get(&d->tree, enum_id, intc_irq_lookup()
73 ptr = radix_tree_lookup(&d->tree, enum_id); intc_irq_lookup()
151 mapped = radix_tree_lookup(&d->tree, subgroup->parent_id); intc_subgroup_init_one()
176 err = radix_tree_insert(&d->tree, entry->enum_id, entry); intc_subgroup_init_one()
180 radix_tree_tag_set(&d->tree, entry->enum_id, intc_subgroup_init_one()
208 nr_found = radix_tree_gang_lookup_tag_slot(&d->tree, intc_subgroup_map()
249 radix_tree_tag_clear(&d->tree, entry->enum_id, intc_subgroup_map()
263 if (radix_tree_tagged(&d->tree, INTC_TAG_VIRQ_NEEDS_ALLOC)) intc_finalize()
/linux-4.1.27/arch/powerpc/include/asm/
H A Dserial.h12 * through the device tree.
15 /* Default baud base if not found in device-tree */
H A Dpte-hash32.h11 * active mappings. We maintain a two-level page table tree, much
15 * tree and putting them into the hash table when necessary, and
16 * updating the accessed and modified bits in the page table tree.
H A Dbootx.h20 /* BootX passes the device-tree using a format that comes from earlier
H A Ddcr-regs.h19 * etc... are obtained for the device tree.
85 * excluded here and configured in the device tree.
107 * excluded here and configured in the device tree.
162 * The base address is configured in the device tree.
/linux-4.1.27/arch/m68k/sun3/prom/
H A Dinit.c18 /* The root node of the prom device tree. */
21 /* Pointer to the device tree operations structure. */
/linux-4.1.27/arch/sparc/crypto/
H A Dcrop_devid.c6 * mechanisms in userspace which scan the OF device tree and
/linux-4.1.27/arch/metag/kernel/
H A Dtime.c16 /* Init clocks from device tree */ time_init()
H A Dclock.c50 * Checks to see if a "core" clock is provided in the device tree, and overrides
84 * Set up important clocks from device tree. In particular any needed for clock
/linux-4.1.27/arch/microblaze/boot/dts/
H A DMakefile17 # Rule to build device tree blobs
/linux-4.1.27/arch/mips/boot/dts/include/dt-bindings/clock/
H A Dberlin2q.h2 * Berlin2 BG2Q clock tree IDs
H A Dberlin2.h2 * Berlin2 BG2/BG2CD clock tree IDs
/linux-4.1.27/arch/mips/boot/dts/include/dt-bindings/leds/
H A Dcommon.h2 * This header provides macros for the common LEDs device tree bindings.
/linux-4.1.27/include/linux/platform_data/
H A Dpinctrl-single.h6 * tree except for omap where there are still some dependencies
/linux-4.1.27/arch/powerpc/boot/dts/include/dt-bindings/clock/
H A Dberlin2q.h2 * Berlin2 BG2Q clock tree IDs
H A Dberlin2.h2 * Berlin2 BG2/BG2CD clock tree IDs
/linux-4.1.27/arch/powerpc/boot/dts/include/dt-bindings/leds/
H A Dcommon.h2 * This header provides macros for the common LEDs device tree bindings.
/linux-4.1.27/arch/arm64/boot/dts/include/dt-bindings/clock/
H A Dberlin2q.h2 * Berlin2 BG2Q clock tree IDs
H A Dberlin2.h2 * Berlin2 BG2/BG2CD clock tree IDs
/linux-4.1.27/arch/arm64/boot/dts/include/dt-bindings/leds/
H A Dcommon.h2 * This header provides macros for the common LEDs device tree bindings.
/linux-4.1.27/arch/metag/boot/dts/include/dt-bindings/clock/
H A Dberlin2q.h2 * Berlin2 BG2Q clock tree IDs
H A Dberlin2.h2 * Berlin2 BG2/BG2CD clock tree IDs
/linux-4.1.27/arch/metag/boot/dts/include/dt-bindings/leds/
H A Dcommon.h2 * This header provides macros for the common LEDs device tree bindings.
/linux-4.1.27/arch/arm/boot/dts/include/dt-bindings/clock/
H A Dberlin2q.h2 * Berlin2 BG2Q clock tree IDs
H A Dberlin2.h2 * Berlin2 BG2/BG2CD clock tree IDs
/linux-4.1.27/arch/arm/boot/dts/include/dt-bindings/leds/
H A Dcommon.h2 * This header provides macros for the common LEDs device tree bindings.
/linux-4.1.27/include/dt-bindings/clock/
H A Dberlin2q.h2 * Berlin2 BG2Q clock tree IDs
H A Dberlin2.h2 * Berlin2 BG2/BG2CD clock tree IDs
/linux-4.1.27/include/dt-bindings/leds/
H A Dcommon.h2 * This header provides macros for the common LEDs device tree bindings.
/linux-4.1.27/fs/jfs/
H A Djfs_dmap.h24 #define TREESIZE (256+64+16+4+1) /* size of a dmap tree */
25 #define LEAFIND (64+16+4+1) /* index of 1st leaf of a dmap tree */
26 #define LPERDMAP 256 /* num leaves per dmap tree */
27 #define L2LPERDMAP 8 /* l2 number of leaves per dmap tree */
33 #define CTLTREESIZE (1024+256+64+16+4+1) /* size of a dmapctl tree */
34 #define CTLLEAFIND (256+64+16+4+1) /* idx of 1st leaf of a dmapctl tree */
35 #define LPERCTL 1024 /* num of leaves per dmapctl tree */
36 #define L2LPERCTL 10 /* l2 num of leaves per dmapctl tree */
37 #define ROOT 0 /* index of the root of a tree */
62 * of the tree.
143 * dmap summary tree
148 __le32 nleafs; /* 4: number of tree leafs */
149 __le32 l2nleafs; /* 4: l2 number of tree leafs */
150 __le32 leafidx; /* 4: index of first tree leaf */
151 __le32 height; /* 4: height of the tree */
152 s8 budmin; /* 1: min l2 tree leaf value to combine */
153 s8 stree[TREESIZE]; /* TREESIZE: tree */
164 struct dmaptree tree; /* 360: dmap tree */ member in struct:dmap
176 __le32 nleafs; /* 4: number of tree leafs */
177 __le32 l2nleafs; /* 4: l2 number of tree leafs */
178 __le32 leafidx; /* 4: index of the first tree leaf */
179 __le32 height; /* 4: height of tree */
180 s8 budmin; /* 1: minimum l2 tree leaf value */
181 s8 stree[CTLTREESIZE]; /* CTLTREESIZE: dmapctl tree */
215 __le32 dn_agstart; /* 4: start tree index at AG height */
234 int dn_agstart; /* start tree index at AG height */
H A Djfs_btree.h22 * jfs_btree.h: B+-tree
24 * JFS B+-tree (dtree and xtree) common definitions
42 #define BT_TYPE 0x07 /* B+-tree index */
/linux-4.1.27/include/net/
H A Dpkt_cls.h207 * struct tcf_ematch_tree - ematch tree handle
209 * @hdr: ematch tree header supplied by userspace
224 * @match: called during ematch tree evaluation, must return 1/0
253 * tcf_em_tree_change - replace ematch tree of a running classifier
256 * @dst: destination ematch tree variable
257 * @src: source ematch tree (temporary tree from tcf_em_tree_validate)
259 * This functions replaces the ematch tree in @dst with the ematch
260 * tree in @src. The classifier in charge of the ematch tree may be
273 * tcf_em_tree_match - evaulate an ematch tree
276 * @tree: ematch tree to be used for evaluation
279 * This function matches @skb against the ematch tree in @tree by going
283 * Returns 1 if the ematch tree as-one matches, no ematches are configured
287 struct tcf_ematch_tree *tree, tcf_em_tree_match()
290 if (tree->hdr.nmatches) tcf_em_tree_match()
291 return __tcf_em_tree_match(skb, tree, info); tcf_em_tree_match()
286 tcf_em_tree_match(struct sk_buff *skb, struct tcf_ematch_tree *tree, struct tcf_pkt_info *info) tcf_em_tree_match() argument
/linux-4.1.27/sound/pci/cs46xx/
H A Dcs46xx_dsp_task_types.h40 | |Goto /| tree header |g /| tree header |g /| tree header |g /| SCB |r
46 | tree |g/ | tree |g/ | tree |g/
64 #define SLEEP_ACTIVE_INCREMENT 0 /* Enable task tree thread to go to sleep
66 #define STANDARD_ACTIVE_INCREMENT 1 /* Task tree thread normal operation */
67 #define SUSPEND_ACTIVE_INCREMENT 2 /* Cause execution to suspend in the task tree thread
122 /* Initial tock count; controls task tree execution rate */
129 Subtract on task tree termination */
132 /* Number of pending activations for task tree */
177 /* This structure contains extra storage for the task tree
180 /* Up to 10 values are saved onto the stack. 8 for the task tree, 1 for
/linux-4.1.27/lib/
H A Dradix-tree.c27 #include <linux/radix-tree.h>
46 * Radix tree node cache.
51 * The radix tree is variable-height, so an insert operation not only has
56 * The worst case is a zero height tree with just a single item at index 0,
245 * ensure that the addition of a single element in the tree cannot fail. On
249 * To make use of this facility, the radix tree must be initialised without
279 * ensure that the addition of a single element in the tree cannot fail. On
283 * To make use of this facility, the radix tree must be initialised without
311 * radix tree with height HEIGHT.
319 * Extend a radix tree so it can store key @index.
370 * __radix_tree_create - create a slot in a radix tree
371 * @root: radix tree root
377 * at position @index in the radix tree @root.
379 * Until there is more than one item in the tree, no nodes are
392 /* Make sure the tree is high enough. */ __radix_tree_create()
436 * radix_tree_insert - insert into a radix tree
437 * @root: radix tree root
441 * Insert an item into the radix tree at position @index.
473 * __radix_tree_lookup - lookup an item in a radix tree
474 * @root: radix tree root
480 * tree @root.
482 * Until there is more than one item in the tree, no nodes are
534 * radix_tree_lookup_slot - lookup a slot in a radix tree
535 * @root: radix tree root
539 * radix tree @root. This is useful for update-if-exists operations.
557 * radix_tree_lookup - perform lookup operation on a radix tree
558 * @root: radix tree root
561 * Lookup the item at the position @index in the radix tree @root.
575 * radix_tree_tag_set - set a tag on a radix tree node
576 * @root: radix tree root
581 * corresponding to @index in the radix tree. From
620 * radix_tree_tag_clear - clear a tag on a radix tree node
621 * @root: radix tree root
626 * corresponding to @index in the radix tree. If
683 * radix_tree_tag_get - get a tag on a radix tree node
684 * @root: radix tree root
742 * @root: radix tree root
774 /* Single-slot tree */ radix_tree_next_chunk()
787 /* Index outside of the tree */ radix_tree_next_chunk()
859 * @root: radix tree root
866 * This function scans range of radix tree from first_index to last_index
951 * back up the tree setting tags, until we update slot to radix_tree_range_tag_if_tagged()
967 * last_index is guaranteed to be in the tree, what radix_tree_range_tag_if_tagged()
987 * radix_tree_gang_lookup - perform multiple lookup on a radix tree
988 * @root: radix tree root
993 * Performs an index-ascending scan of the tree for present items. Places
1001 * an atomic snapshot of the tree at a single point in time, the semantics
1033 * radix_tree_gang_lookup_slot - perform multiple slot lookup on radix tree
1034 * @root: radix tree root
1040 * Performs an index-ascending scan of the tree for present items. Places
1075 * radix_tree_gang_lookup_tag - perform multiple lookup on a radix tree
1077 * @root: radix tree root
1083 * Performs an index-ascending scan of the tree for present items which
1117 * radix tree based on a tag
1118 * @root: radix tree root
1124 * Performs an index-ascending scan of the tree for present items which
1199 * radix_tree_locate_item - search through radix tree for item
1200 * @root: radix tree root
1247 * radix_tree_shrink - shrink height of a radix tree to minimal
1248 * @root radix tree root
1252 /* try to shrink tree height */ radix_tree_shrink()
1271 * moving the node from one part of the tree to another: if it radix_tree_shrink()
1312 * @root: radix tree root
1315 * After clearing the slot at @index in @node from radix tree
1317 * node and shrinking the tree.
1361 * radix_tree_delete_item - delete an item from a radix tree
1362 * @root: radix tree root
1366 * Remove @item at @index from the radix tree rooted at @root.
1414 * radix_tree_delete - delete an item from a radix tree
1415 * @root: radix tree root
1418 * Remove the item at @index from the radix tree rooted at @root.
1429 * radix_tree_tagged - test whether any items in the tree are tagged
1430 * @root: radix tree root
H A Dinterval_tree_test.c53 printk(KERN_ALERT "interval tree insert/remove"); interval_tree_test_init()
73 printk(KERN_ALERT "interval tree search"); interval_tree_test_init()
/linux-4.1.27/scripts/dtc/libfdt/
H A Dlibfdt.h68 * tree, but its buffer did not have sufficient space to
69 * contain the expanded tree. Use fdt_open_into() to move the
70 * device tree to a buffer with more space. */
86 * tree created by the sequential-write functions, which is
89 /* Error codes: codes for bad device tree blobs */
91 /* FDT_ERR_TRUNCATED: Structure block of the given device tree
94 /* FDT_ERR_BADMAGIC: Given "device tree" appears not to be a
95 * device tree at all - it is missing the flattened device
96 * tree magic number. */
98 /* FDT_ERR_BADVERSION: Given device tree has a version which
101 * required to convert the tree to the expected version. */
103 /* FDT_ERR_BADSTRUCTURE: Given device tree has a corrupt
108 * device tree has it's sub-blocks in an order that the
110 * then strings). Use fdt_open_into() to reorganize the tree
175 * fdt_check_header - sanity check a device tree or possible device tree
176 * @fdt: pointer to data which might be a flattened device tree
179 * appears to be a flattened device tree with sane information in its
183 * 0, if the buffer appears to contain a valid device tree
191 * fdt_move - move a device tree around in memory
192 * @fdt: pointer to the device tree to move
196 * fdt_move() relocates, if possible, the device tree blob located at
198 * with the existing device tree blob at fdt. Therefore,
204 * -FDT_ERR_NOSPACE, bufsize is insufficient to contain the device tree
216 * fdt_string - retrieve a string from the strings block of a device tree
217 * @fdt: pointer to the device tree blob
221 * strings block of the device tree blob at fdt.
231 * @fdt: pointer to the device tree blob
233 * Returns the number of entries in the device tree blob's memory
244 * @fdt: pointer to the device tree blob
248 * the n-th reserve map entry from the device tree blob, in
261 * @fdt: pointer to the device tree blob
275 * @fdt: pointer to the device tree blob
299 * fdt_path_offset - find a tree node by its full path
300 * @fdt: pointer to the device tree blob
303 * fdt_path_offset() finds a node of a given path in the device tree.
324 * @fdt: pointer to the device tree blob
329 * device tree node at structure block offset nodeoffset. If lenp is
347 * @fdt: pointer to the device tree blob
367 * @fdt: pointer to the device tree blob
388 * @fdt: pointer to the device tree blob
393 * fdt_property structure within the device tree blob at the given
416 * @fdt: pointer to the device tree blob
432 * @fdt: pointer to the device tree blob
438 * structure within the device tree blob corresponding to the property
469 * @fdt: pointer to the device tree blob
480 * by namep (this will be a pointer to within the device tree's string
503 * @fdt: pointer to the device tree blob
517 * @fdt: pointer to the device tree blob
552 * @fdt: pointer to the device tree blob
555 * fdt_get_phandle() retrieves the phandle of the device tree node at
566 * @fdt: pointer to the device tree blob
578 * @fdt: pointer to the device tree blob
592 * @fdt: pointer to the device tree blob
600 * NOTE: This function is expensive, as it must scan the device tree
619 * @fdt: pointer to the device tree blob
633 * NOTE: This function is expensive, as it must scan the device tree
652 * @fdt: pointer to the device tree blob
658 * NOTE: This function is expensive, as it must scan the device tree
673 * @fdt: pointer to the device tree blob
680 * NOTE: This function is expensive, as it must scan the device tree
696 * @fdt: pointer to the device tree blob
705 * startoffset is -1, the very first such node in the tree.
725 * tree after startoffset
738 * @fdt: pointer to the device tree blob
743 * in the tree with the given phandle (an invalid tree), results are
759 * @fdt: pointer to the device tree blob
760 * @nodeoffset: offset of a tree node
784 * @fdt: pointer to the device tree blob
791 * very first such node in the tree.
809 * tree after startoffset
825 * @fdt: pointer to the device tree blob
838 * of the tree.
856 * @fdt: pointer to the device tree blob
869 * of the tree.
891 * @fdt: pointer to the device tree blob
904 * of the tree.
937 * @fdt: pointer to the device tree blob
943 * tree.
947 * tree.
963 * @fdt: pointer to the device tree blob
968 * effectively removing it from the tree.
972 * move any other part of the tree.
1023 * @fdt: pointer to the device tree blob
1047 * @fdt: pointer to the device tree blob
1071 * @fdt: pointer to the device tree blob
1097 * @fdt: pointer to the device tree blob
1128 * @fdt: pointer to the device tree blob
1163 * @fdt: pointer to the device tree blob
1209 * @fdt: pointer to the device tree blob
1240 * @fdt: pointer to the device tree blob
1270 * @fdt: pointer to the device tree blob
1305 * @fdt: pointer to the device tree blob
1351 * @fdt: pointer to the device tree blob
1381 * @fdt: pointer to the device tree blob
1405 * @fdt: pointer to the device tree blob
1420 * @fdt: pointer to the device tree blob
1451 * @fdt: pointer to the device tree blob
/linux-4.1.27/include/linux/
H A Dradix-tree.h46 * A common use of the radix tree is to store pointers to struct pages;
47 * but shmem/tmpfs needs also to store swap entries in the same tree:
59 /*** radix-tree API starts here ***/
92 /* Used when ascending tree */
94 /* For tree user */
100 /* For tree user */
130 * Radix-tree synchronization
132 * The radix-tree API requires that users provide all synchronisation (with
135 * Synchronization of access to the data items being stored in the tree, and
139 * - any function _modifying_ the tree or tags (inserting or deleting
141 * exclude any functions reading the tree.
142 * - any function _reading_ the tree or tags (looking up items or tags,
143 * gang lookups) must exclude modifications to the tree, but may occur
166 * the radix tree *and* a synchronize_rcu() grace period).
169 * access to data items when inserting into or looking up from the radix tree)
187 * For use with radix_tree_lookup_slot(). Caller must hold tree at least read
200 * radix_tree_deref_slot_protected - dereference a slot without RCU lock but with tree lock held
207 * must hold the tree lock to prevent parallel updates.
254 * For use with radix_tree_lookup_slot(). Caller must hold tree write locked
310 * struct radix_tree_iter - radix tree iterator state
316 * This radix tree iterator works in terms of "chunks" of slots. A chunk is a
317 * subinterval of slots contained within one radix tree leaf node. It is
319 * which holds the chunk's position in the tree and its size. For tagged
321 * radix tree tag.
334 * radix_tree_iter_init - initialize radix tree iterator
359 * @root: radix tree root
364 * This function looks up the next chunk in the radix tree starting from
366 * Also it fills @iter with data about chunk: position in the tree (index),
376 * If we iterate over a tree protected only by the RCU lock, a race
391 * @iter: pointer to radix tree iterator
468 * @slot points to the radix tree slot, @iter->index contains its index.
481 * @slot points to radix tree slot, @iter->index contains its index.
496 * @slot points to radix tree slot, @iter->index contains its index.
514 * @slot points to radix tree slot, @iter->index contains its index.
H A Dof_fdt.h18 /* Definitions used by the flattened device tree */
27 /* For scanning an arbitrary device-tree at any time */
51 /* For scanning the flat device-tree at boot time */
73 /* Early flat tree scan hooks */
H A Dof_pdt.h2 * Definitions for building a device tree by calling into the
39 /* for building the device tree */
H A Dreset-controller.h34 * @of_node: corresponding device tree node as phandle target
37 * device tree to id as given to the reset control ops
H A Dassoc_array_priv.h35 * An N-way node in the tree.
47 * The tree is optimised for search-by-ID, but permits reasonable iteration
50 * The tree is navigated by constructing an index key consisting of an array of
53 * The segments correspond to levels of the tree (the first segment is used at
105 * Internal tree member pointers are marked in the bottom one or two bits to
H A Dbtree.h12 * is described at http://en.wikipedia.org/wiki/B-tree, we currently do not
18 * tree entries.
30 * @node: the first node in the tree
32 * @height: current of the tree
145 * @target: the tree that gets all the entries
146 * @victim: the tree that gets merged into @target
168 * of that entry; returns NULL if the tree is empty, in that case
H A Dfmc-sdb.h36 extern signed long fmc_find_sdb_device(struct sdb_array *tree, uint64_t vendor,
H A Dirqdomain.h8 * irq_domains also have a hook for translating device tree interrupt
21 * we use an open firmware device-tree. We do have references to struct
37 #include <linux/radix-tree.h>
55 * @xlate: Given a device tree node and interrupt specifier, decode
96 * @of_node: Pointer to device tree nodes associated with the irq_domain. Used
97 * when decoding device tree interrupt specifiers.
107 * @revmap_tree: Radix map tree for hwirqs that don't fit in the linear map
169 * @of_node: pointer to interrupt controller's device tree node.
225 * using the radix tree.
H A Dswapops.h4 #include <linux/radix-tree.h>
8 * swapcache pages are stored in the swapper_space radix tree. We want to
9 * get good packing density in that tree, so the index should be dense in
/linux-4.1.27/drivers/of/
H A Doverlay.c2 * Functions for working with device tree overlays
103 /* create empty tree as a target */ of_overlay_apply_single_device_node()
165 * live tree is reverted to the state before the attempt.
254 * @tree: Device node containing all the overlays
256 * Helper function that given a tree containing overlay information,
264 struct device_node *tree) of_build_overlay_info()
272 for_each_child_of_node(tree, node) of_build_overlay_info()
280 for_each_child_of_node(tree, node) { for_each_child_of_node()
330 * @tree: Device node containing all the overlays
338 int of_overlay_create(struct device_node *tree) of_overlay_create() argument
357 pr_err("%s: idr_alloc() failed for tree@%s\n", of_overlay_create()
358 __func__, tree->full_name); of_overlay_create()
365 err = of_build_overlay_info(ov, tree); of_overlay_create()
367 pr_err("%s: of_build_overlay_info() failed for tree@%s\n", of_overlay_create()
368 __func__, tree->full_name); of_overlay_create()
375 pr_err("%s: of_overlay_apply() failed for tree@%s\n", of_overlay_create()
376 __func__, tree->full_name); of_overlay_create()
383 pr_err("%s: of_changeset_apply() failed for tree@%s\n", of_overlay_create()
384 __func__, tree->full_name); of_overlay_create()
409 /* check whether the given node, lies under the given tree */ overlay_subtree_check()
410 static int overlay_subtree_check(struct device_node *tree, overlay_subtree_check() argument
416 if (tree == dn) overlay_subtree_check()
419 for_each_child_of_node(tree, child) { for_each_child_of_node()
263 of_build_overlay_info(struct of_overlay *ov, struct device_node *tree) of_build_overlay_info() argument
H A Dfdt.c35 * Adjust the flattened device tree to have at most 'limit' number of
82 * @blob: A device tree blob
113 * @blob: A device tree blob
164 * unflatten_dt_node - Alloc and populate a device_node from the flat tree
165 * @blob: The parent device tree blob
167 * @p: pointer to node in flat tree
273 /* We accept flattened tree phandles either in unflatten_dt_node()
284 * used in pSeries dynamic device tree unflatten_dt_node()
370 * __unflatten_device_tree - create tree of device_nodes from flat blob
372 * unflattens a device-tree, creating the
373 * tree of struct device_node. It also fills the "name" and "type"
374 * pointers of the nodes so the normal device-tree walking functions
377 * @mynodes: The device_node tree created by the call
379 * for the resulting tree
392 pr_debug("No device tree pointer\n"); __unflatten_device_tree()
396 pr_debug("Unflattening device tree:\n"); __unflatten_device_tree()
402 pr_err("Invalid device tree blob header\n"); __unflatten_device_tree()
413 /* Allocate memory for the expanded device tree */ __unflatten_device_tree()
425 pr_warning("End of tree marker overwritten: %08x\n", __unflatten_device_tree()
437 * of_fdt_unflatten_tree - create tree of device_nodes from flat blob
439 * unflattens the device-tree passed by the firmware, creating the
440 * tree of struct device_node. It also fills the "name" and "type"
441 * pointers of the nodes so the normal device-tree walking functions
572 * defined in device tree structures. It should be called by arch specific code
601 * of_scan_flat_dt - scan flattened tree blob and call callback on each.
605 * This function is used to scan the flattened device-tree, it is
607 * unflatten the tree
726 pr_err("\n unrecognized device tree list:\n[ "); of_flat_dt_match_machine()
747 * early_init_dt_check_for_initrd - Decode initrd location from flat tree
1034 /* check device tree validity */ early_init_dt_verify()
1038 /* Setup flat device-tree pointer */ early_init_dt_verify()
1071 * unflatten_device_tree - create tree of device_nodes from flat blob
1073 * unflattens the device-tree passed by the firmware, creating the
1074 * tree of struct device_node. It also fills the "name" and "type"
1075 * pointers of the nodes so the normal device-tree walking functions
1088 * unflatten_and_copy_device_tree - copy and create tree of device_nodes from flat blob
1090 * Copies and unflattens the device-tree passed by the firmware, creating the
1091 * tree of struct device_node. It also fills the "name" and "type"
1092 * pointers of the nodes so the normal device-tree walking functions
1104 pr_warn("No valid device tree found, continuing without\n"); unflatten_and_copy_device_tree()
H A Dof_pci_irq.c12 * device-node exists for a given pci_dev, it will use normal OF tree
14 * PCI tree until an device-node is found, at which point it will finish
15 * resolving using the OF tree walking.
26 * device tree parsing of_irq_parse_pci()
46 /* Now we walk up the PCI tree */ of_irq_parse_pci()
94 * of_irq_parse_and_map_pci() - Decode a PCI irq from the device tree and map to a virq
H A Dof_net.c51 * Search the device tree for the best MAC address to use. 'mac-address' is
55 * 'address' is checked, just in case we're using an old device tree.
62 * exist in the device tree, but were not set by U-Boot. For example, the
H A Dplatform.c42 * @np: Pointer to device tree node
61 * mechanism for creating devices from device tree nodes.
66 * @dev: pointer to device structure that is linked to a device tree node
355 * device tree files. of_platform_bus_create()
378 * of_platform_bus_probe() - Probe the device-tree for platform buses
379 * @root: parent of the first level to probe or NULL for the root of the tree
417 * of_platform_populate() - Populate platform_devices from device tree data
418 * @root: parent of the first level to probe or NULL for the root of the tree
423 * Similar to of_platform_bus_probe(), this function walks the device tree
461 /* Do not touch devices not populated from the device tree */ of_platform_device_destroy()
483 * of_platform_depopulate() - Remove devices populated from device tree
488 * created from their respective device tree nodes (and only those,
H A Dof_mdio.c9 * out of the OpenFirmware device tree and using it to populate an mii_bus.
114 * of_mdiobus_register - Register mii_bus and create PHYs from the device tree
129 * the device tree are populated after the bus has been registered */ of_mdiobus_register()
194 * @phy_np: Pointer to the phy's device tree node
210 * of_phy_connect - Connect to the phy described in the device tree
212 * @phy_np: Pointer to device tree node for the PHY
H A Dirq.c17 * device tree to actual irq numbers on an interrupt controller
81 * of_irq_parse_raw - Low level interrupt tree parsing
88 * This function is a low-level interrupt tree walking function. It
92 * input, walks the tree looking for any interrupt-map properties, translates
112 * is none, we are nice and just walk up the tree of_irq_parse_raw()
160 /* Now start the actual "proper" walk of the interrupt tree */ of_irq_parse_raw()
284 * This function resolves an interrupt for a node by walking the interrupt tree,
357 * @dev: pointer to device tree node
389 * @dev: pointer to device tree node
416 * @dev: pointer to device tree node
439 * @dev: pointer to device tree node
454 * @dev: pointer to device tree node
483 * This function scans the device tree for matching interrupt controller nodes,
H A Dresolver.c51 * Find live tree's maximum phandle value.
208 * Does not take any devtree locks so make sure you call this on a tree
292 * of_resolve - Resolve the given node against the live tree.
296 * Perform dynamic Device Tree resolution against the live tree
297 * to the given node to resolve. This depends on the live tree
301 * are fit to be inserted or operate upon the live tree.
/linux-4.1.27/drivers/block/drbd/
H A Ddrbd_interval.c44 * drbd_insert_interval - insert a new interval into a tree
80 * drbd_contains_interval - check if a tree contains a given interval
84 * Returns if the tree contains the node @interval with start sector @start.
86 * in @tree. Returns %false if @interval is in the tree but with a different
114 * drbd_remove_interval - remove an interval from a tree
129 * tree, the interval with the lowest start sector is returned, and all other
130 * overlapping intervals will be on the right side of the tree, reachable with
/linux-4.1.27/arch/powerpc/include/uapi/asm/
H A Dbootx.h63 * Note that the kernel arguments and the device tree are appended
82 /* The device tree (internal addresses relative to the beginning of the tree,
83 * device tree offset relative to the beginning of this structure).
87 __u32 deviceTreeOffset; /* Device tree offset */
88 __u32 deviceTreeSize; /* Size of the device tree */
111 device-tree. */
122 /* Total params size (args + colormap + device tree + ramdisk) */
/linux-4.1.27/drivers/eisa/
H A DMakefile1 # Makefile for the Linux device tree
/linux-4.1.27/drivers/base/
H A DMakefile1 # Makefile for the Linux device tree
/linux-4.1.27/arch/powerpc/boot/
H A Dsimpleboot.c3 * tree or any platform configuration information.
4 * All data is extracted from an embedded device tree
37 fatal("Invalid device tree blob\n"); platform_init()
83 /* prepare the device tree and find the console */ platform_init()
H A Dprpmc2800.c312 printf("Using device tree defaults...\n\r"); prpmc2800_get_bip()
346 /* Get the cpu -> pci i/o & mem mappings from the device tree */ prpmc2800_bridge_setup()
350 " device tree node\n\r"); prpmc2800_bridge_setup()
357 /* Get the cpu -> pci i/o & mem mappings from the device tree */ prpmc2800_bridge_setup()
360 fatal("Error: Missing marvell,mv64360 device tree node\n\r"); prpmc2800_bridge_setup()
412 * defaults already in the device tree. prpmc2800_fixups()
417 /* Know the board type so override device tree defaults */ prpmc2800_fixups()
421 fatal("Error: Missing '/' device tree node\n\r"); prpmc2800_fixups()
434 fatal("Error: Missing proper cpu device tree node\n\r"); prpmc2800_fixups()
441 fatal("Error: Missing /memory device tree node\n\r"); prpmc2800_fixups()
451 " device tree node\n\r"); prpmc2800_fixups()
458 fatal("Error: Missing User FLASH device tree node\n\r"); prpmc2800_fixups()
H A Depapr.c42 printf("WARNING: Device tree address is outside IMA!" platform_fixups()
46 printf("WARNING: Device tree extends outside IMA!" platform_fixups()
H A Dmain.c61 * bootwrapper. The device tree has been moved in fdt_init() prep_kernel()
71 "device tree\n\r"); prep_kernel()
131 /* Tell the kernel initrd address via device tree */ prep_initrd()
198 /* Ensure that the device tree has a /chosen node */ start()
208 printf("Finalizing device tree..."); start()
212 printf(" flat tree at 0x%lx\n\r", ft_addr); start()
214 printf(" using OF tree (promptr=%p)\n\r", loader_info.promptr); start()
H A Dcuboot-c2k.c56 fatal("Error: Missing marvell,mv64360 device tree node\n\r"); c2k_bridge_setup()
62 /* Get the cpu -> pci i/o & mem mappings from the device tree */ c2k_bridge_setup()
85 /* Get the cpu -> pci i/o & mem mappings from the device tree */ c2k_bridge_setup()
H A Dcuboot.c2 * Compatibility for old (not device tree aware) U-Boot versions
H A Dlibfdt-wrapper.c3 * device tree operations and the interface provided by shared source
67 fatal("Couldn't find %d bytes to expand device tree\n\r", size); expand_buf()
165 fatal("Couldn't pack flat tree: %s\n\r", fdt_wrapper_finalize()
191 fatal("malloc failed. can't relocate the device tree\n\r"); fdt_init()
H A Dplanetcore.h36 /* Updates the device tree local-mac-address properties based
/linux-4.1.27/arch/arc/kernel/
H A Dclk.c14 * As of now we default to device-tree provided clock
/linux-4.1.27/drivers/gpu/drm/nouveau/nvkm/core/
H A Dhandle.c45 list_for_each_entry(item, &handle->tree, head) { nvkm_handle_init()
55 list_for_each_entry_continue_reverse(item, &handle->tree, head) { nvkm_handle_init()
71 list_for_each_entry(item, &handle->tree, head) { nvkm_handle_fini()
88 list_for_each_entry_continue_reverse(item, &handle->tree, head) { nvkm_handle_fini()
114 INIT_LIST_HEAD(&handle->tree); nvkm_handle_create()
140 list_add(&handle->head, &handle->parent->tree); nvkm_handle_create()
156 list_for_each_entry_safe(item, temp, &handle->tree, head) { nvkm_handle_destroy()
/linux-4.1.27/fs/ocfs2/
H A Dalloc.h31 * For xattr tree leaf, we limit the leaf byte size to be 64K.
37 * the b-tree operations in ocfs2. Now all the b-tree operations are not
39 * to store can use b-tree. And it only needs to implement its ocfs2_extent_tree
42 * ocfs2_extent_tree becomes the first-class object for extent tree
46 * ocfs2_extent_tree contains info for the root of the b-tree, it must have a
47 * root ocfs2_extent_list and a root_bh so that they can be used in the b-tree
49 * I/O on the tree. With metadata ecc, we now call different journal_access
53 * the root of extent b-tree.
154 * of extent tree. So for an inode, it should be &fe->id2.i_list. Otherwise
162 * maximal limit. That's a tree depth shift. So, one block for ocfs2_extend_meta_needed()
163 * level of the tree (current l_tree_depth), one block for the ocfs2_extend_meta_needed()
165 * top-of-the tree. ocfs2_extend_meta_needed()
280 * The idea here is to be as generic as possible with the tree
H A Duptodate.c173 unsigned int tree, to_purge, purged; ocfs2_metadata_cache_purge() local
179 tree = !(ci->ci_flags & OCFS2_CACHE_FL_INLINE); ocfs2_metadata_cache_purge()
184 to_purge, tree); ocfs2_metadata_cache_purge()
186 /* If we're a tree, save off the root so that we can safely ocfs2_metadata_cache_purge()
187 * initialize the cache. We do the work to free tree members ocfs2_metadata_cache_purge()
189 if (tree) ocfs2_metadata_cache_purge()
199 if (tree && purged != to_purge) ocfs2_metadata_cache_purge()
317 * exist in the tree.
360 /* tree should be exactly OCFS2_CACHE_INFO_MAX_ARRAY wide. NULL the
361 * pointers in tree after we use them - this allows caller to detect
366 struct ocfs2_meta_cache_item **tree) ocfs2_expand_cache()
378 /* Be careful to initialize the tree members *first* because ocfs2_expand_cache()
381 tree[i]->c_block = ci->ci_cache.ci_array[i]; ocfs2_expand_cache()
389 __ocfs2_insert_cache_tree(ci, tree[i]); ocfs2_expand_cache()
390 tree[i] = NULL; ocfs2_expand_cache()
406 struct ocfs2_meta_cache_item *tree[OCFS2_CACHE_INFO_MAX_ARRAY] = __ocfs2_set_buffer_uptodate() local
424 tree[i] = kmem_cache_alloc(ocfs2_uptodate_cachep, __ocfs2_set_buffer_uptodate()
426 if (!tree[i]) { __ocfs2_set_buffer_uptodate()
445 ocfs2_expand_cache(ci, tree); __ocfs2_set_buffer_uptodate()
457 if (tree[0]) { __ocfs2_set_buffer_uptodate()
459 if (tree[i]) __ocfs2_set_buffer_uptodate()
461 tree[i]); __ocfs2_set_buffer_uptodate()
468 * a tree, the code will not recheck after acquiring the lock --
469 * multiple paths cannot be expanding to a tree at the same time.
472 * (including the whole tree wiped and reset) when this process it out
510 /* We need to bump things up to a tree. */ ocfs2_set_buffer_uptodate()
365 ocfs2_expand_cache(struct ocfs2_caching_info *ci, struct ocfs2_meta_cache_item **tree) ocfs2_expand_cache() argument
H A Drefcounttree.c206 struct ocfs2_refcount_tree *tree = NULL; ocfs2_find_refcount_tree() local
209 tree = rb_entry(n, struct ocfs2_refcount_tree, rf_node); ocfs2_find_refcount_tree()
211 if (blkno < tree->rf_blkno) ocfs2_find_refcount_tree()
213 else if (blkno > tree->rf_blkno) ocfs2_find_refcount_tree()
216 return tree; ocfs2_find_refcount_tree()
253 static void ocfs2_free_refcount_tree(struct ocfs2_refcount_tree *tree) ocfs2_free_refcount_tree() argument
255 ocfs2_metadata_cache_exit(&tree->rf_ci); ocfs2_free_refcount_tree()
256 ocfs2_simple_drop_lockres(OCFS2_SB(tree->rf_sb), &tree->rf_lockres); ocfs2_free_refcount_tree()
257 ocfs2_lock_res_free(&tree->rf_lockres); ocfs2_free_refcount_tree()
258 kfree(tree); ocfs2_free_refcount_tree()
263 struct ocfs2_refcount_tree *tree) ocfs2_erase_refcount_tree_from_list_no_lock()
265 rb_erase(&tree->rf_node, &osb->osb_rf_lock_tree); ocfs2_erase_refcount_tree_from_list_no_lock()
266 if (osb->osb_ref_tree_lru && osb->osb_ref_tree_lru == tree) ocfs2_erase_refcount_tree_from_list_no_lock()
271 struct ocfs2_refcount_tree *tree) ocfs2_erase_refcount_tree_from_list()
274 ocfs2_erase_refcount_tree_from_list_no_lock(osb, tree); ocfs2_erase_refcount_tree_from_list()
280 struct ocfs2_refcount_tree *tree = ocfs2_kref_remove_refcount_tree() local
283 ocfs2_free_refcount_tree(tree); ocfs2_kref_remove_refcount_tree()
287 ocfs2_refcount_tree_get(struct ocfs2_refcount_tree *tree) ocfs2_refcount_tree_get() argument
289 kref_get(&tree->rf_getcnt); ocfs2_refcount_tree_get()
293 ocfs2_refcount_tree_put(struct ocfs2_refcount_tree *tree) ocfs2_refcount_tree_put() argument
295 kref_put(&tree->rf_getcnt, ocfs2_kref_remove_refcount_tree); ocfs2_refcount_tree_put()
336 struct ocfs2_refcount_tree *tree, *new = NULL; ocfs2_get_refcount_tree() local
343 tree = osb->osb_ref_tree_lru; ocfs2_get_refcount_tree()
345 tree = ocfs2_find_refcount_tree(osb, rf_blkno); ocfs2_get_refcount_tree()
346 if (tree) ocfs2_get_refcount_tree()
358 * We need the generation to create the refcount tree lock and since ocfs2_get_refcount_tree()
359 * it isn't changed during the tree modification, we are safe here to ocfs2_get_refcount_tree()
380 tree = ocfs2_find_refcount_tree(osb, rf_blkno); ocfs2_get_refcount_tree()
381 if (tree) ocfs2_get_refcount_tree()
386 tree = new; ocfs2_get_refcount_tree()
390 *ret_tree = tree; ocfs2_get_refcount_tree()
392 osb->osb_ref_tree_lru = tree; ocfs2_get_refcount_tree()
425 struct ocfs2_refcount_tree *tree, int rw) __ocfs2_lock_refcount_tree()
429 ret = ocfs2_refcount_lock(tree, rw); __ocfs2_lock_refcount_tree()
436 down_write(&tree->rf_sem); __ocfs2_lock_refcount_tree()
438 down_read(&tree->rf_sem); __ocfs2_lock_refcount_tree()
445 * Lock the refcount tree pointed by ref_blkno and return the tree.
446 * In most case, we lock the tree and read the refcount block.
449 * If the tree has been re-created by other node, it will free the
458 struct ocfs2_refcount_tree *tree = NULL; ocfs2_lock_refcount_tree() local
463 ret = ocfs2_get_refcount_tree(osb, ref_blkno, &tree); ocfs2_lock_refcount_tree()
469 ocfs2_refcount_tree_get(tree); ocfs2_lock_refcount_tree()
471 ret = __ocfs2_lock_refcount_tree(osb, tree, rw); ocfs2_lock_refcount_tree()
474 ocfs2_refcount_tree_put(tree); ocfs2_lock_refcount_tree()
478 ret = ocfs2_read_refcount_block(&tree->rf_ci, tree->rf_blkno, ocfs2_lock_refcount_tree()
482 ocfs2_unlock_refcount_tree(osb, tree, rw); ocfs2_lock_refcount_tree()
483 ocfs2_refcount_tree_put(tree); ocfs2_lock_refcount_tree()
490 * to recreate the refcount tree also. ocfs2_lock_refcount_tree()
492 * Here we just remove the tree from the rb-tree, and the last ocfs2_lock_refcount_tree()
495 * the new refcount tree for us. ocfs2_lock_refcount_tree()
497 if (tree->rf_generation != le32_to_cpu(rb->rf_generation)) { ocfs2_lock_refcount_tree()
498 if (!tree->rf_removed) { ocfs2_lock_refcount_tree()
499 ocfs2_erase_refcount_tree_from_list(osb, tree); ocfs2_lock_refcount_tree()
500 tree->rf_removed = 1; ocfs2_lock_refcount_tree()
504 ocfs2_unlock_refcount_tree(osb, tree, rw); ocfs2_lock_refcount_tree()
507 * tree, so another put will destroy it. ocfs2_lock_refcount_tree()
510 ocfs2_refcount_tree_put(tree); ocfs2_lock_refcount_tree()
516 *ret_tree = tree; ocfs2_lock_refcount_tree()
527 struct ocfs2_refcount_tree *tree, int rw) ocfs2_unlock_refcount_tree()
530 up_write(&tree->rf_sem); ocfs2_unlock_refcount_tree()
532 up_read(&tree->rf_sem); ocfs2_unlock_refcount_tree()
534 ocfs2_refcount_unlock(tree, rw); ocfs2_unlock_refcount_tree()
535 ocfs2_refcount_tree_put(tree); ocfs2_unlock_refcount_tree()
541 struct ocfs2_refcount_tree *tree; ocfs2_purge_refcount_trees() local
545 tree = rb_entry(node, struct ocfs2_refcount_tree, rf_node); ocfs2_purge_refcount_trees()
548 (unsigned long long) tree->rf_blkno); ocfs2_purge_refcount_trees()
550 rb_erase(&tree->rf_node, root); ocfs2_purge_refcount_trees()
551 ocfs2_free_refcount_tree(tree); ocfs2_purge_refcount_trees()
556 * Create a refcount tree for an inode.
570 struct ocfs2_refcount_tree *new_tree = NULL, *tree = NULL; ocfs2_create_refcount_tree() local
659 * We have to init the tree lock here since it will use ocfs2_create_refcount_tree()
667 tree = ocfs2_find_refcount_tree(osb, first_blkno); ocfs2_create_refcount_tree()
670 * We've just created a new refcount tree in this block. If ocfs2_create_refcount_tree()
671 * we found a refcount tree on the ocfs2_super, it must be ocfs2_create_refcount_tree()
672 * one we just deleted. We free the old tree before ocfs2_create_refcount_tree()
673 * inserting the new tree. ocfs2_create_refcount_tree()
675 BUG_ON(tree && tree->rf_generation == new_tree->rf_generation); ocfs2_create_refcount_tree()
676 if (tree) ocfs2_create_refcount_tree()
677 ocfs2_erase_refcount_tree_from_list_no_lock(osb, tree); ocfs2_create_refcount_tree()
681 if (tree) ocfs2_create_refcount_tree()
682 ocfs2_refcount_tree_put(tree); ocfs2_create_refcount_tree()
927 * Try to remove refcount tree. The mechanism is:
931 * 4) Remove the tree.
1002 * the subroot. Otherwise we may corrupt the b-tree. ocfs2_get_refcount_cpos_end()
1106 "refcount tree %llu has non zero tree " ocfs2_get_refcount_rec()
1107 "depth in leaf btree tree block %llu\n", ocfs2_get_refcount_rec()
1418 * But we will use the low 32 bit to be the e_cpos in the b-tree.
1633 * the old root bh hasn't been expanded to a b-tree, ocfs2_expand_refcount_tree()
1648 /* Now add a new refcount block into the tree.*/ ocfs2_expand_refcount_tree()
1659 * Adjust the extent rec in b-tree representing ref_leaf_bh.
1829 * This is much simple than our b-tree code.
2299 /* Caller must hold refcount tree lock. */ ocfs2_decrease_refcount()
2310 struct ocfs2_refcount_tree *tree; ocfs2_decrease_refcount() local
2320 ret = ocfs2_get_refcount_tree(OCFS2_SB(inode->i_sb), ref_blkno, &tree); ocfs2_decrease_refcount()
2326 ret = ocfs2_read_refcount_block(&tree->rf_ci, tree->rf_blkno, ocfs2_decrease_refcount()
2333 ret = __ocfs2_decrease_refcount(handle, &tree->rf_ci, ref_root_bh, ocfs2_decrease_refcount()
2365 "tree, but the feature bit is not set in the " ocfs2_mark_extent_refcounted()
2495 * So we may need ref_blocks to insert into the tree. ocfs2_calc_refcount_meta_credits()
2496 * That also means we need to change the b-tree and add that number ocfs2_calc_refcount_meta_credits()
2525 * For refcount tree, we will decrease some contiguous clusters
2534 * Caller must hold refcount tree lock.
2546 struct ocfs2_refcount_tree *tree; ocfs2_prepare_refcount_change_for_del() local
2551 "tree, but the feature bit is not set in the " ocfs2_prepare_refcount_change_for_del()
2560 refcount_loc, &tree); ocfs2_prepare_refcount_change_for_del()
2566 ret = ocfs2_read_refcount_block(&tree->rf_ci, refcount_loc, ocfs2_prepare_refcount_change_for_del()
2574 &tree->rf_ci, ocfs2_prepare_refcount_change_for_del()
2645 * get good I/O from the resulting extent tree.
2678 "Inode %lu has non zero tree depth in " ocfs2_refcount_cal_cow_clusters()
2849 * clusters(starting form p_cluster) in the refcount tree.
2852 * 1. since we may split the old tree, so we at most will need num_clusters + 2
3382 "tree, but the feature bit is not set in the " ocfs2_replace_cow()
3554 * refcount tree change if we truncate it to 0.
3700 * Insert a new extent into refcount tree and mark a extent rec
3701 * as refcounted in the dinode tree.
262 ocfs2_erase_refcount_tree_from_list_no_lock(struct ocfs2_super *osb, struct ocfs2_refcount_tree *tree) ocfs2_erase_refcount_tree_from_list_no_lock() argument
270 ocfs2_erase_refcount_tree_from_list(struct ocfs2_super *osb, struct ocfs2_refcount_tree *tree) ocfs2_erase_refcount_tree_from_list() argument
424 __ocfs2_lock_refcount_tree(struct ocfs2_super *osb, struct ocfs2_refcount_tree *tree, int rw) __ocfs2_lock_refcount_tree() argument
526 ocfs2_unlock_refcount_tree(struct ocfs2_super *osb, struct ocfs2_refcount_tree *tree, int rw) ocfs2_unlock_refcount_tree() argument
H A Drefcounttree.h38 struct ocfs2_refcount_tree **tree,
41 struct ocfs2_refcount_tree *tree,
63 * Some refcount caller need to do more work after we modify the data b-tree
/linux-4.1.27/drivers/staging/lustre/lustre/ldlm/
H A Dldlm_extent.c123 /* interval tree, for LDLM_EXTENT. */ ldlm_interval_attach()
160 /** Add newly granted lock into interval tree for the resource. */ ldlm_extent_add_lock()
195 /* even though we use interval tree to manage the extent lock, we also ldlm_extent_add_lock()
200 /** Remove cancelled lock from resource interval tree. */ ldlm_extent_unlink_lock()
205 struct ldlm_interval_tree *tree; ldlm_extent_unlink_lock() local
213 tree = &res->lr_itree[idx]; ldlm_extent_unlink_lock()
215 LASSERT(tree->lit_root != NULL); /* assure the tree is not null */ ldlm_extent_unlink_lock()
217 tree->lit_size--; ldlm_extent_unlink_lock()
220 interval_erase(&node->li_node, &tree->lit_root); ldlm_extent_unlink_lock()
/linux-4.1.27/scripts/
H A Dtags.sh23 tree=
25 tree=${srctree}/
29 ignore="$ignore ( -path ${tree}tools ) -prune -o"
35 for arch in `ls ${tree}arch`; do
53 find ${tree}arch/$1 $ignore $subarchprune $prune -name "$2" \
60 include=$(find ${tree}arch/$1/ $subarchprune \
71 find ${tree}include $ignore -name config -prune -o -name "$1" \
75 # find sources in rest of tree
79 find ${tree}* $ignore \
297 subarchdir=$(find ${tree}arch/$SRCARCH/ -name "mach-*" -type d -o \
H A Dcheckkconfigsymbols.py44 "current tree. Please note that specifying commits will " \
45 "\'git reset --hard\'\nyour current tree! You may save " \
63 help="Reset current Git tree even when it's dirty.")
76 sys.exit("The current Git tree is dirty (see 'git status'). "
79 " Please run this script in a clean Git tree or pass "
130 # default to check the entire tree
148 """Return true if the current working tree is dirty (i.e., if any file has
/linux-4.1.27/arch/sparc/kernel/
H A Dcpumap.c42 int start_index; /* Index of first node of a level in a cpuinfo tree */
43 int end_index; /* Index of last node of a level in a cpuinfo tree */
44 int num_nodes; /* Number of nodes in a level in a cpuinfo tree */
50 /* Offsets into nodes[] for each level of the tree */
62 /* Niagara optimized cpuinfo tree traversal. */
84 /* Generic cpuinfo tree traversal. Distribute work round robin across NUMA
120 * end index, and number of nodes for each level in the cpuinfo tree. The
121 * total number of cpuinfo nodes required to build the tree is returned.
179 /* Build a tree representation of the CPU hierarchy using the per CPU
206 /* Initialize all levels in the tree with the first CPU */ build_cpuinfo_tree()
259 /* Connect tree node to parent */ build_cpuinfo_tree()
364 * tree is being built. _cpu_map_rebuild()
370 /* Fallback if the cpuinfo tree could not be built. CPU mapping is linear
/linux-4.1.27/arch/powerpc/kernel/
H A Dpci_of_scan.c2 * Helper routines to scan the device tree for PCI devices and busses
23 * get_int_prop - Decode a u32 from a device tree property
37 * pci_parse_of_flags - Parse the flags cell of a device tree PCI address
38 * @addr0: value of 1st cell of a device tree PCI address.
67 * of_pci_parse_addrs - Parse PCI addresses assigned in the device tree node
68 * @node: device tree node for the PCI device
72 * device tree node and writes them into the associated pci_dev structure.
119 * of_create_pci_dev - Given a device tree node on a pci bus, create a pci_dev
120 * @node: device tree node pointer
122 * @devfn: PCI function number, extracted from device tree by caller.
347 * @node: device tree node for the PCI bus
385 * @node: device tree node for the PCI bus
396 * @node: device tree node for the PCI bus
H A Deeh_cache.c34 * PCI device address resources into a red-black tree, sorted
45 * (Implementation Note: The RB tree seems to be better/faster
126 /* Insert address range into the rb tree. */
135 /* Walk tree, find a place to insert into tree */ eeh_addr_cache_insert()
198 /* Walk resources on this device, poke them into the tree */ __eeh_addr_cache_insert_dev()
257 * Remove a device from the addr-cache tree.
259 * the tree multiple times (once per resource).
305 /* Verify tree built up above, echo back the list of addrs. */
H A Dprom.c2 * Procedures for creating, accessing and interpreting the device tree.
107 * move_device_tree - move tree to an unused area, if needed.
109 * The device tree may be allocated beyond our memory limit, or inside the
129 DBG("Moved device tree to 0x%p\n", p); move_device_tree()
560 * the very first block in the device-tree as it represents early_init_dt_add_memory_arch()
656 panic("BUG: Failed verifying flat device tree, bad version?"); early_init_devtree()
669 /* scan tree to see if dump is active during last boot */ early_init_devtree()
674 * device-tree, including the platform type, initrd location and early_init_devtree()
714 /* We may need to relocate the flat tree, do it now. early_init_devtree()
722 /* Retrieve CPU related informations from the flat tree early_init_devtree()
753 /* Setup flat device-tree pointer */ early_get_first_memblock_info()
773 * object, call of_node_put() when done. The device tree and list
/linux-4.1.27/drivers/md/bcache/
H A Dbset.c252 * the auxiliar search tree - when we're done searching the bset_float tree we
256 * we're touching one fewer cacheline in the bset tree in exchange for one more
299 kfree(t->tree); bch_btree_keys_free()
301 free_pages((unsigned long) t->tree, bch_btree_keys_free()
307 t->tree = NULL; bch_btree_keys_free()
324 t->tree = bset_tree_bytes(b) < PAGE_SIZE bch_btree_keys_alloc()
327 if (!t->tree) bch_btree_keys_alloc()
365 /* Binary tree stuff for auxiliary search trees */
396 * Given a binary tree constructed in an array (i.e. how you normally implement
397 * a heap), it converts a node in the tree - referenced by array index - to the
402 * The binary tree starts at array index 1, not 0
487 * t->tree is a binary search tree in an array; each node corresponds to a key
491 * the binary tree points to; to_inorder() gives us the cacheline, and then
500 * of the previous key so we can walk backwards to it from t->tree[j]'s key.
523 return cacheline_to_bkey(t, to_inorder(j, t), t->tree[j].m); tree_to_bkey()
533 * maintain a full search tree, we just keep a simple lookup table in t->prev.
556 struct bkey_float *f = &t->tree[j]; make_bfloat()
595 t->tree = t[-1].tree + j; bset_alloc_tree()
612 if (t->tree != b->set->tree + btree_keys_cachelines(b)) { bch_bset_build_unwritten_tree()
646 b->set->tree + btree_keys_cachelines(b) - t->tree); bch_bset_build_written_tree()
663 t->tree[j].m = bkey_to_cacheline_offset(t, cacheline++, k); bch_bset_build_written_tree()
671 /* Then we build the tree */ bch_bset_build_written_tree()
762 if (t->size == b->set->tree + btree_keys_cachelines(b) - t->tree) bch_bset_fix_lookup_table()
842 /* prev is in the tree, if we merge we're done */ bch_btree_insert_key()
902 prefetch(&t->tree[p]); bset_search_tree()
905 f = &t->tree[j]; bset_search_tree()
935 f = &t->tree[inorder_next(j, t->size)]; bset_search_tree()
943 f = &t->tree[inorder_prev(j, t->size)]; bset_search_tree()
962 * * The set is too small to have a search tree, so we just do a linear __bch_bset_search()
965 * auxiliary search tree up to date would be too expensive, so we __bch_bset_search()
968 * * Or we use the auxiliary search tree we constructed earlier - __bch_bset_search()
977 * Each node in the auxiliary search tree covers a certain range __bch_bset_search()
1324 if (t->tree[j].exponent == 127) bch_btree_keys_stats()
H A Dbset.h76 * into, we construct a binary search tree in an array - traversing a binary
77 * search tree in an array gives excellent locality of reference and is very
85 * when traversing this tree.
87 * Nodes in the auxiliary search tree must contain both a key to compare against
92 * search tree corresponds to precisely BSET_CACHELINE bytes in the set. We have
93 * a function (to_inorder()) that takes the index of a node in a binary tree and
99 * search tree at every iteration we know that both our search key and the key
102 * at the root of the tree).
110 * key our auxiliary search tree node corresponds to, and key p, the key
112 * search tree is the highest bit that differs between n and p.
115 * comparison. But we'd really like our nodes in the auxiliary search tree to be
126 * The keys in the auxiliary search tree are stored in (software) floating
137 * don't want to be constantly rebuilding the search tree for the last set
158 * We construct a binary tree in an array as if the array
164 /* size of the binary tree and prev array */
172 struct bkey_float *tree; member in struct:bset_tree
175 * The nodes in the bset tree point to specific keys - this
217 * Sets of sorted keys - the real btree node - plus a binary search tree
219 * set[0] is special; set[0]->tree, set[0]->prev and set[0]->data point
/linux-4.1.27/arch/metag/include/asm/mach/
H A Darch.h24 * @dt_compat: Array of device tree 'compatible' strings.
36 * It is chosen by matching the compatible strings in the device tree provided
38 * the machine that aren't configured with device tree (yet).
/linux-4.1.27/drivers/gpu/drm/nouveau/include/nvkm/core/
H A Dhandle.h11 struct list_head tree; member in struct:nvkm_handle
/linux-4.1.27/arch/mips/boot/dts/include/dt-bindings/thermal/
H A Dthermal_exynos.h2 * thermal_exynos.h - Samsung EXYNOS TMU device tree definitions
/linux-4.1.27/drivers/acpi/acpica/
H A Dpswalk.c3 * Module Name: pswalk - Parser routines to walk parsed op tree(s)
55 * PARAMETERS: subtree_root - Root of tree (or subtree) to delete
59 * DESCRIPTION: Delete a portion of or an entire parse tree.
83 /* Still going downward in tree (Op is not completed yet) */ acpi_ps_delete_parse_tree()
/linux-4.1.27/fs/quota/
H A Dquota_tree.h23 #define QT_TREEOFF 1 /* Offset of tree in file in blocks */
H A Dquotaio_v2.h34 * (as it appears on disk) - the file is a radix tree whose leaves point
73 #define V2_DQBLKSIZE_BITS 10 /* Size of leaf block in tree */
/linux-4.1.27/arch/openrisc/kernel/
H A Dprom.c17 * interpreting the device tree.
H A Dsetup.c173 panic("No compatible CPU found in device tree...\n"); setup_cpuinfo()
192 "Device tree missing CPU 'clock-frequency' parameter." setup_cpuinfo()
205 * Handles the pointer to the device tree that this kernel is to use
208 * Falls back on built-in device tree in case null pointer is passed.
265 * from the clock frequency passed in via the device tree
276 panic("no cpu 'clock-frequency' parameter in device tree"); calibrate_delay()
/linux-4.1.27/arch/powerpc/boot/dts/include/dt-bindings/thermal/
H A Dthermal_exynos.h2 * thermal_exynos.h - Samsung EXYNOS TMU device tree definitions
/linux-4.1.27/arch/arm64/boot/dts/include/dt-bindings/thermal/
H A Dthermal_exynos.h2 * thermal_exynos.h - Samsung EXYNOS TMU device tree definitions
/linux-4.1.27/arch/metag/boot/dts/include/dt-bindings/thermal/
H A Dthermal_exynos.h2 * thermal_exynos.h - Samsung EXYNOS TMU device tree definitions
/linux-4.1.27/arch/arm/boot/dts/include/dt-bindings/thermal/
H A Dthermal_exynos.h2 * thermal_exynos.h - Samsung EXYNOS TMU device tree definitions
/linux-4.1.27/security/selinux/
H A DMakefile2 # Makefile for building the SELinux module as part of the kernel tree.
/linux-4.1.27/include/dt-bindings/thermal/
H A Dthermal_exynos.h2 * thermal_exynos.h - Samsung EXYNOS TMU device tree definitions
/linux-4.1.27/arch/sparc/prom/
H A Dinit_32.c22 /* The root node of the prom device tree. */
26 /* Pointer to the device tree operations structure. */
H A Dinit_64.c20 /* The root node of the prom device tree. */
H A Dmp.c17 /* Start cpu with prom-tree node 'cpunode' using context described
/linux-4.1.27/drivers/ata/
H A Dpata_of_platform.c40 "device tree\n"); pata_of_platform_probe()
47 "device tree\n"); pata_of_platform_probe()
/linux-4.1.27/arch/powerpc/platforms/44x/
H A Debony.c10 * Rewritten and ported to the merged powerpc tree:
48 * Called very early, MMU is off, device-tree isn't unflattened
H A Diss4xx.c13 * Rewritten and ported to the merged powerpc tree:
72 * device-tree, just pass 0 to all arguments iss4xx_init_irq()
99 * the device-tree but currently there's little point as it's smp_iss4xx_kick_cpu()
148 * Called very early, MMU is off, device-tree isn't unflattened
H A Dppc44x_simple.c45 * as they most certainly are not from a device tree perspective.
46 * However, their differences are handled by the device tree and the
/linux-4.1.27/arch/mips/kernel/
H A Dprom.c2 * MIPS support for CONFIG_OF device tree support
64 panic("device tree not present"); __dt_register_buses()
/linux-4.1.27/arch/nios2/boot/
H A DMakefile34 # Rule to build device tree blobs
50 # Rule to build device tree blobs with make command
/linux-4.1.27/arch/metag/include/asm/
H A Dclock.h22 * If a "core" clock is provided by the device tree, it
32 * Perform platform clock initialisation, reading clocks from device tree etc.
/linux-4.1.27/drivers/firewire/
H A Dcore-topology.c137 * setting the gap count. As we build the tree bottom up in
144 * containted in a child tree, in which case the max hop count is just
177 * This function builds the tree representation of the topology given
179 * of the tree, the function checks that the self IDs are valid and
404 struct fw_node *tree; move_tree() local
407 tree = node1->ports[port]; move_tree()
408 node0->ports[port] = tree; move_tree()
409 for (i = 0; i < tree->port_count; i++) { move_tree()
410 if (tree->ports[i] == node1) { move_tree()
411 tree->ports[i] = node0; move_tree()
418 * Compare the old topology tree for card with the new one specified by root.
420 * Update the nodes in the card topology tree as we go.
487 * the tree and queue FW_NODE_CREATED update_tree()
/linux-4.1.27/drivers/net/ethernet/mellanox/mlx4/
H A Dsrq.c8 * COPYING in the main directory of this source tree, or the
50 srq = radix_tree_lookup(&srq_table->tree, srqn & (dev->caps.num_srqs - 1)); mlx4_srq_event()
179 err = radix_tree_insert(&srq_table->tree, srq->srqn, srq); mlx4_srq_alloc()
216 radix_tree_delete(&srq_table->tree, srq->srqn); mlx4_srq_alloc()
235 radix_tree_delete(&srq_table->tree, srq->srqn); mlx4_srq_free()
281 INIT_RADIX_TREE(&srq_table->tree, GFP_ATOMIC); mlx4_init_srq_table()
307 srq = radix_tree_lookup(&srq_table->tree, mlx4_srq_lookup()
H A Dcq.c11 * COPYING in the main directory of this source tree, or the
104 cq = radix_tree_lookup(&mlx4_priv(dev)->cq_table.tree, mlx4_cq_completion()
123 cq = radix_tree_lookup(&cq_table->tree, cqn & (dev->caps.num_cqs - 1)); mlx4_cq_event()
305 err = radix_tree_insert(&cq_table->tree, cq->cqn, cq); mlx4_cq_alloc()
351 radix_tree_delete(&cq_table->tree, cq->cqn); mlx4_cq_alloc()
374 radix_tree_delete(&cq_table->tree, cq->cqn); mlx4_cq_free()
391 INIT_RADIX_TREE(&cq_table->tree, GFP_ATOMIC); mlx4_init_cq_table()
/linux-4.1.27/drivers/net/ethernet/mellanox/mlx5/core/
H A Dcq.c7 * COPYING in the main directory of this source tree, or the
48 cq = radix_tree_lookup(&table->tree, cqn); mlx5_cq_completion()
73 cq = radix_tree_lookup(&table->tree, cqn); mlx5_cq_event()
116 err = radix_tree_insert(&table->tree, cq->cqn, cq); mlx5_core_create_cq()
147 tmp = radix_tree_delete(&table->tree, cq->cqn); mlx5_core_destroy_cq()
150 mlx5_core_warn(dev, "cq 0x%x not found in tree\n", cq->cqn); mlx5_core_destroy_cq()
228 INIT_RADIX_TREE(&table->tree, GFP_ATOMIC); mlx5_init_cq_table()
H A Dmr.c7 * COPYING in the main directory of this source tree, or the
44 INIT_RADIX_TREE(&table->tree, GFP_ATOMIC); mlx5_init_mr_table()
93 /* connect to MR tree */ mlx5_core_create_mkey()
95 err = radix_tree_insert(&table->tree, mlx5_base_mkey(mr->key), mr); mlx5_core_create_mkey()
98 mlx5_core_warn(dev, "failed radix tree insert of mr 0x%x, %d\n", mlx5_core_create_mkey()
120 deleted_mr = radix_tree_delete(&table->tree, mlx5_base_mkey(mr->key)); mlx5_core_destroy_mkey()
123 mlx5_core_warn(dev, "failed radix tree delete of mr 0x%x\n", mlx5_core_destroy_mkey()
H A Dsrq.c7 * COPYING in the main directory of this source tree, or the
48 srq = radix_tree_lookup(&table->tree, srqn); mlx5_srq_event()
72 srq = radix_tree_lookup(&table->tree, srqn); mlx5_core_get_srq()
106 err = radix_tree_insert(&table->tree, srq->srqn, srq); mlx5_core_create_srq()
134 tmp = radix_tree_delete(&table->tree, srq->srqn); mlx5_core_destroy_srq()
137 mlx5_core_warn(dev, "srq 0x%x not found in tree\n", srq->srqn); mlx5_core_destroy_srq()
217 INIT_RADIX_TREE(&table->tree, GFP_ATOMIC); mlx5_init_srq_table()
/linux-4.1.27/drivers/fmc/
H A Dfmc-sdb.c253 signed long fmc_find_sdb_device(struct sdb_array *tree, fmc_find_sdb_device() argument
260 int i, n = tree->len; fmc_find_sdb_device()
265 r = &tree->record[i]; fmc_find_sdb_device()
269 if (!IS_ERR(tree->subtree[i])) fmc_find_sdb_device()
270 res = fmc_find_sdb_device(tree->subtree[i], fmc_find_sdb_device()
273 return res + tree->baseaddr; fmc_find_sdb_device()
285 return first + tree->baseaddr; fmc_find_sdb_device()
/linux-4.1.27/fs/ubifs/
H A Dshrinker.c25 * tree when Linux VM needs more RAM.
29 * just walks the TNC tree when searching for znodes to free.
31 * If the root of a TNC sub-tree is clean and old enough, then the children are
61 * shrink_tnc - shrink TNC tree.
67 * This function traverses TNC tree and frees clean znodes. It does not free
83 * Traverse the TNC tree in levelorder manner, so that it is possible shrink_tnc()
110 * Also note, if the root of a sub-tree is not in 'c->cnext', shrink_tnc()
111 * then the whole sub-tree is not in 'c->cnext' as well, so it shrink_tnc()
112 * is safe to dump whole sub-tree. shrink_tnc()
/linux-4.1.27/kernel/locking/
H A Drtmutex_common.h43 * @tree_entry: pi node to enqueue into the mutex waiters tree
44 * @pi_tree_entry: pi node to enqueue into the mutex owner waiters tree
61 * Various helpers to access the waiters-tree:
/linux-4.1.27/drivers/memory/
H A Dof_memory.c22 * @np: pointer to ddr device tree node
26 * from device tree node. Returns a pointer to the populated
96 * @np_ddr: Pointer to ddr device tree node
103 * tree node. Returns pointer to populated structure. If any error
/linux-4.1.27/drivers/staging/rtl8712/
H A Dethernet.h18 * Modifications for inclusion into the Linux staging tree are
/linux-4.1.27/drivers/staging/lustre/lustre/include/
H A Dinterval_tree.h50 in_intree:1, /** set if the node is in tree */
94 * nodes in the tree will be set to @node before the callback being called
105 /* Search the extents in the tree and call @func for each overlapped
111 /* Iterate every node in the tree - by reverse order or regular order. */
/linux-4.1.27/drivers/pinctrl/
H A Ddevicetree.h2 * Internal interface to pinctrl device tree integration
/linux-4.1.27/arch/x86/include/asm/
H A Dprom.h2 * Definitions for Device tree / OpenFirmware handling on X86
/linux-4.1.27/arch/microblaze/kernel/
H A Dirq.c51 /* process the entire interrupt tree in one go */ init_IRQ()
/linux-4.1.27/drivers/md/persistent-data/
H A Ddm-btree.h85 * Number of nested btrees. (Not the depth of a single tree.)
92 * Set up an empty tree. O(1).
97 * Delete a tree. O(n) - this is the slow one! It can also block, so
122 * tree.
/linux-4.1.27/arch/powerpc/platforms/512x/
H A Dmpc512x_generic.c37 * Called very early, MMU is off, device-tree isn't unflattened
/linux-4.1.27/arch/powerpc/platforms/83xx/
H A Dasp834x.c42 * Called very early, MMU is off, device-tree isn't unflattened
H A Dmpc831x_rdb.c45 * Called very early, MMU is off, device-tree isn't unflattened
H A Dmpc836x_rdk.c44 * Called very early, MMU is off, device-tree isn't unflattened.
/linux-4.1.27/arch/powerpc/platforms/85xx/
H A Dbsc913x_rdb.c48 * Called very early, device-tree isn't unflattened
H A Dqemu_e500.c4 * This is intended to be a flexible device-tree-driven platform, not fixed
61 * Called very early, device-tree isn't unflattened
H A Dmpc85xx_ds.c168 * Called very early, device-tree isn't unflattened
186 * Called very early, device-tree isn't unflattened
196 * Called very early, device-tree isn't unflattened
/linux-4.1.27/arch/c6x/include/asm/
H A Ddscr.h23 * controlled should be a property in the device's tree node.
/linux-4.1.27/arch/arm/mach-s3c24xx/
H A Dmach-s3c2416-dt.c2 * Samsung's S3C2416 flattened device tree enabled machine
/linux-4.1.27/arch/arm/mm/
H A Dcache-aurora-l2.h52 * coming from the device tree */
/linux-4.1.27/arch/alpha/kernel/
H A Dgct.c38 /* Now walk the tree, siblings first. */ gct6_find_nodes()
/linux-4.1.27/arch/arc/plat-arcfpga/
H A Dplatform.c19 * however as part of early device tree scan, we also select the right
/linux-4.1.27/tools/perf/util/
H A Dquote.h20 * sprintf(cmd, "git-diff-tree %s %s", sq_quote(arg0), sq_quote(arg1));
H A Dcallchain.h34 struct rb_node rb_node; /* to sort nodes in an output tree */
35 struct rb_root rb_root_in; /* input tree of children */
36 struct rb_root rb_root; /* sorted output tree of children */
/linux-4.1.27/include/linux/i2c/
H A Di2c-hid.h22 * driver, or the flattened device tree) to setup the irq related to the gpio in
/linux-4.1.27/fs/autofs4/
H A Dexpire.c121 * Calculate and dget next entry in top down tree traversal.
185 * Direct mounts have similar expiry semantics to tree mounts.
186 * The tree is not busy iff no mountpoints are busy and there are no
211 /* Check a directory tree of mount points for busyness
212 * The tree is not busy iff no mountpoints are busy
262 /* Timeout of a tree mount is ultimately determined by its top dentry */ autofs4_tree_busy()
295 /* Check if we can expire a direct mount (possibly a tree) */ autofs4_expire_direct()
391 /* Case 2: tree mount, expire iff entire tree is not busy */ should_expire()
421 * Find an eligible tree to time-out
422 * A tree is eligible if :-
/linux-4.1.27/fs/dlm/
H A Ddebug_fs.c424 struct rb_root *tree; table_seq_start() local
453 tree = toss ? &ls->ls_rsbtbl[bucket].toss : &ls->ls_rsbtbl[bucket].keep; table_seq_start()
456 if (!RB_EMPTY_ROOT(tree)) { table_seq_start()
457 for (node = rb_first(tree); node; node = rb_next(node)) { table_seq_start()
485 tree = toss ? &ls->ls_rsbtbl[bucket].toss : &ls->ls_rsbtbl[bucket].keep; table_seq_start()
488 if (!RB_EMPTY_ROOT(tree)) { table_seq_start()
489 node = rb_first(tree); table_seq_start()
506 struct rb_root *tree; table_seq_next() local
550 tree = toss ? &ls->ls_rsbtbl[bucket].toss : &ls->ls_rsbtbl[bucket].keep; table_seq_next()
553 if (!RB_EMPTY_ROOT(tree)) { table_seq_next()
554 next = rb_first(tree); table_seq_next()
/linux-4.1.27/fs/nilfs2/
H A Dbtree.h2 * btree.h - NILFS B-tree.
34 * struct nilfs_btree_path - A path on which B-tree operations are executed
/linux-4.1.27/arch/powerpc/platforms/40x/
H A Dppc40x_simple.c46 * as they most certainly are not from a device tree perspective.
47 * However, their differences are handled by the device tree and the
/linux-4.1.27/arch/powerpc/platforms/52xx/
H A Dmpc5200_simple.c22 * and if there is a PCI bus node defined in the device tree.
69 * Called very early, MMU is off, device-tree isn't unflattened
/linux-4.1.27/arch/powerpc/platforms/pseries/
H A Devent_sources.c55 /* Else use normal interrupt tree parsing */ request_event_sources_irqs()
57 /* First try to do a proper OF tree parsing */ request_event_sources_irqs()
/linux-4.1.27/arch/mips/pistachio/
H A Dinit.c58 panic("Device-tree not present"); plat_mem_setup()
124 panic("Device tree not present"); plat_of_setup()
/linux-4.1.27/arch/nios2/kernel/
H A Dprom.c2 * Device tree support
7 * Based on MIPS support for CONFIG_OF device tree support
H A Dcpuinfo.c95 "device tree icache-size\n", setup_cpuinfo()
102 "device tree dcache-line-size\n", setup_cpuinfo()
108 "device tree dcache-size\n", setup_cpuinfo()
/linux-4.1.27/arch/m68k/include/asm/
H A Doplib.h28 /* Root node of the prom device tree, this stays constant after
33 /* Pointer to prom structure containing the device tree traversal
121 /* Acquire the IDPROM of the root node in the prom device tree. This
177 /* Start the CPU with the given device tree node, context table, and context
183 /* Stop the CPU with the passed device tree node. */
186 /* Idle the CPU with the passed device tree node. */
189 /* Re-Start the CPU with the passed device tree node. */
210 /* PROM device tree traversal functions... */
/linux-4.1.27/arch/x86/mm/
H A Dpat_rbtree.c7 * Interval tree (augmented rbtree) used to store the PAT memory type
25 * The memtype tree keeps track of memory type for specific
29 * The tree is an interval tree (augmented rbtree) with tree ordered
75 /* Find the first (lowest start addr) overlapping range from rb tree */ memtype_rb_lowest_match()
/linux-4.1.27/fs/hpfs/
H A Dhpfs.h273 /* A directory is a tree of dnodes. The fnode for a directory
274 contains one pointer, to the root dnode of the tree. The fnode
275 never moves, the dnodes do the B-tree thing, splitting and merging
365 /* B+ tree: allocation info in fnodes and anodes */
371 At any rate, fnodes contain a small tree; if subtrees are needed
372 they occupy essentially a full block in anodes. A leaf-level tree node
402 bit 7 - 1 -> (internal) tree of anodes
427 /* fnode: root of allocation b+ tree, and EA's */
454 struct bplus_header btree; /* b+ tree, 8 extents or 12 subtrees */
486 /* anode: 99.44% pure allocation tree */
496 struct bplus_header btree; /* b+tree, 40 extents or 60 subtrees */
510 sector run outside the fnode, or to multiple runs with an anode tree
515 anode tree, pointed to by the value field of the (name,value) pair.
540 if this.anode, the above sector number is the root of an anode tree
/linux-4.1.27/arch/parisc/mm/
H A Dfault.c125 while (tree != vm_avl_empty) {
126 if (tree->vm_start > addr) {
127 tree = tree->vm_avl_left;
129 prev = tree;
134 tree = tree->vm_avl_right;
/linux-4.1.27/drivers/dma/
H A Dof-dma.c2 * Device tree helpers for DMA request / controller
26 * @dma_spec: pointer to DMA specifier as found in the device tree
117 * @dma_spec: pointer to DMA specifier as found in the device tree
201 * @dma_spec: pointer to DMA specifier as found in the device tree
229 * @dma_spec: pointer to DMA specifier as found in the device tree
/linux-4.1.27/arch/sparc/include/asm/
H A Doplib_32.h30 /* Root node of the prom device tree, this stays constant after
35 /* Pointer to prom structure containing the device tree traversal
78 /* Acquire the IDPROM of the root node in the prom device tree. This
102 /* Start the CPU with the given device tree node, context table, and context
111 /* PROM device tree traversal functions... */
H A Doplib_64.h16 /* Root node of the prom device tree, this stays constant after
24 /* /chosen node of the prom device tree, this stays constant after
92 /* Acquire the IDPROM of the root node in the prom device tree. This
107 /* Start the CPU with the given device tree node at the passed program
126 /* Resume the CPU with the passed device tree node. */
179 /* PROM device tree traversal functions... */
/linux-4.1.27/drivers/clk/keystone/
H A Dpll.c159 * @node: device tree node for this clock
229 * @node: device tree node for this clock
240 * @node: device tree node for this clock
251 * @node: device tree node for this clock
295 * @node: device tree node for this clock
/linux-4.1.27/drivers/mtd/ubi/
H A Dubi.h167 * @u.rb: link in the corresponding (free/used) RB-tree
186 * struct ubi_ltree_entry - an entry in the lock tree.
187 * @rb: links RB-tree nodes
196 * &struct ubi_ltree_entry object is inserted to the lock tree (@ubi->ltree).
449 * @ltree_lock: protects the lock tree and @global_sqnum
450 * @ltree: the lock tree
467 * @used: RB-tree of used physical eraseblocks
468 * @erroneous: RB-tree of erroneous used physical eraseblocks
469 * @free: RB-tree of free physical eraseblocks
471 * @scrub: RB-tree of physical eraseblocks which need scrubbing
638 * @u: unions RB-tree or @list links
639 * @u.rb: link in the per-volume RB-tree of &struct ubi_ainf_peb objects
674 * @rb: link in the volume RB-tree
675 * @root: root of the RB-tree containing all the eraseblock belonging to this
696 * @volumes: root of the volume RB-tree
935 * ubi_for_each_free_peb - walk the UBI free RB tree.
938 * @pos: a pointer to RB-tree entry type to use as a loop counter
944 * ubi_for_each_used_peb - walk the UBI used RB tree.
947 * @pos: a pointer to RB-tree entry type to use as a loop counter
953 * ubi_for_each_scub_peb - walk the UBI scub RB tree.
956 * @pos: a pointer to RB-tree entry type to use as a loop counter
972 * ubi_rb_for_each_entry - walk an RB-tree.
974 * @pos: a pointer to RB-tree entry type to use as a loop counter
975 * @root: RB-tree's root
976 * @member: the name of the 'struct rb_node' within the RB-tree entry
986 * ubi_move_aeb_to_list - move a PEB from the volume tree to a list.
/linux-4.1.27/drivers/mtd/
H A Dofpart.c2 * Flash partitions described by the OF (or flattened) device tree
134 pr_warning("Device tree uses obsolete partition map binding: %s\n", parse_ofoldpart_partitions()
191 MODULE_DESCRIPTION("Parser for MTD partitioning information in device tree");
/linux-4.1.27/drivers/mfd/
H A Dintel_msic.c29 * MSIC interrupt tree is readable from SRAM at INTEL_MSIC_IRQ_PHYS_BASE.
47 * @irq_base: base address of the mapped MSIC SRAM interrupt tree
285 * intel_msic_irq_read - read a register from an MSIC interrupt tree
292 * a register value from the MSIC interrupt tree. In this way subdevice
293 * drivers don't have to map in the interrupt tree themselves but can just
413 * Map in the MSIC interrupt tree area in SRAM. This is exposed to intel_msic_probe()
/linux-4.1.27/drivers/staging/skein/
H A Dskein_base.h109 ** Skein APIs for "extended" initialization: MAC keys, tree hashing.
130 ** Skein APIs for MAC and tree hash:
150 ** helpful for other uses of Skein (e.g., tree hash mode).
158 #define SKEIN_T1_POS_TREE_LVL SKEIN_T1_BIT(112) /* 112..118 hash tree level */
169 /* tweak word tweak[1]: tree level bit field mask */
235 ** These are useful for partial input bytes, hash tree init/update, etc.
/linux-4.1.27/drivers/firmware/efi/libstub/
H A Dfdt.c43 pr_efi_err(sys_table, "Truncated device tree! foo!\n"); update_fdt()
102 /* Set initrd address/end in device tree, if present */ update_fdt()
229 pr_efi_err(sys_table, "Unable to allocate memory for new device tree.\n"); allocate_new_fdt_and_exit_boot()
256 * device tree, so free existing buffer that is allocate_new_fdt_and_exit_boot()
259 * on the device tree buffer. allocate_new_fdt_and_exit_boot()
265 pr_efi_err(sys_table, "Unable to constuct new device tree.\n"); allocate_new_fdt_and_exit_boot()
/linux-4.1.27/drivers/infiniband/core/
H A Dumem_rbtree.c7 * COPYING in the main directory of this source tree, or the
56 /* Note that the representation of the intervals in the interval tree

Completed in 4053 milliseconds

1234567891011