1 // SPDX-License-Identifier: GPL-2.0 2 /* 3 * linux/fs/hfs/bnode.c 4 * 5 * Copyright (C) 2001 6 * Brad Boyer (flar@allandria.com) 7 * (C) 2003 Ardis Technologies <roman@ardistech.com> 8 * 9 * Handle basic btree node operations 10 */ 11 12 #include <linux/pagemap.h> 13 #include <linux/slab.h> 14 #include <linux/swap.h> 15 16 #include "btree.h" 17 18 void hfs_bnode_read(struct hfs_bnode *node, void *buf, int off, int len) 19 { 20 struct page *page; 21 int pagenum; 22 int bytes_read; 23 int bytes_to_read; 24 25 off += node->page_offset; 26 pagenum = off >> PAGE_SHIFT; 27 off &= ~PAGE_MASK; /* compute page offset for the first page */ 28 29 for (bytes_read = 0; bytes_read < len; bytes_read += bytes_to_read) { 30 if (pagenum >= node->tree->pages_per_bnode) 31 break; 32 page = node->page[pagenum]; 33 bytes_to_read = min_t(int, len - bytes_read, PAGE_SIZE - off); 34 35 memcpy_from_page(buf + bytes_read, page, off, bytes_to_read); 36 37 pagenum++; 38 off = 0; /* page offset only applies to the first page */ 39 } 40 } 41 42 u16 hfs_bnode_read_u16(struct hfs_bnode *node, int off) 43 { 44 __be16 data; 45 // optimize later... 46 hfs_bnode_read(node, &data, off, 2); 47 return be16_to_cpu(data); 48 } 49 50 u8 hfs_bnode_read_u8(struct hfs_bnode *node, int off) 51 { 52 u8 data; 53 // optimize later... 54 hfs_bnode_read(node, &data, off, 1); 55 return data; 56 } 57 58 void hfs_bnode_read_key(struct hfs_bnode *node, void *key, int off) 59 { 60 struct hfs_btree *tree; 61 int key_len; 62 63 tree = node->tree; 64 if (node->type == HFS_NODE_LEAF || 65 tree->attributes & HFS_TREE_VARIDXKEYS) 66 key_len = hfs_bnode_read_u8(node, off) + 1; 67 else 68 key_len = tree->max_key_len + 1; 69 70 hfs_bnode_read(node, key, off, key_len); 71 } 72 73 void hfs_bnode_write(struct hfs_bnode *node, void *buf, int off, int len) 74 { 75 struct page *page; 76 77 off += node->page_offset; 78 page = node->page[0]; 79 80 memcpy_to_page(page, off, buf, len); 81 set_page_dirty(page); 82 } 83 84 void hfs_bnode_write_u16(struct hfs_bnode *node, int off, u16 data) 85 { 86 __be16 v = cpu_to_be16(data); 87 // optimize later... 88 hfs_bnode_write(node, &v, off, 2); 89 } 90 91 void hfs_bnode_write_u8(struct hfs_bnode *node, int off, u8 data) 92 { 93 // optimize later... 94 hfs_bnode_write(node, &data, off, 1); 95 } 96 97 void hfs_bnode_clear(struct hfs_bnode *node, int off, int len) 98 { 99 struct page *page; 100 101 off += node->page_offset; 102 page = node->page[0]; 103 104 memzero_page(page, off, len); 105 set_page_dirty(page); 106 } 107 108 void hfs_bnode_copy(struct hfs_bnode *dst_node, int dst, 109 struct hfs_bnode *src_node, int src, int len) 110 { 111 struct page *src_page, *dst_page; 112 113 hfs_dbg(BNODE_MOD, "copybytes: %u,%u,%u\n", dst, src, len); 114 if (!len) 115 return; 116 src += src_node->page_offset; 117 dst += dst_node->page_offset; 118 src_page = src_node->page[0]; 119 dst_page = dst_node->page[0]; 120 121 memcpy_page(dst_page, dst, src_page, src, len); 122 set_page_dirty(dst_page); 123 } 124 125 void hfs_bnode_move(struct hfs_bnode *node, int dst, int src, int len) 126 { 127 struct page *page; 128 void *ptr; 129 130 hfs_dbg(BNODE_MOD, "movebytes: %u,%u,%u\n", dst, src, len); 131 if (!len) 132 return; 133 src += node->page_offset; 134 dst += node->page_offset; 135 page = node->page[0]; 136 ptr = kmap_local_page(page); 137 memmove(ptr + dst, ptr + src, len); 138 kunmap_local(ptr); 139 set_page_dirty(page); 140 } 141 142 void hfs_bnode_dump(struct hfs_bnode *node) 143 { 144 struct hfs_bnode_desc desc; 145 __be32 cnid; 146 int i, off, key_off; 147 148 hfs_dbg(BNODE_MOD, "bnode: %d\n", node->this); 149 hfs_bnode_read(node, &desc, 0, sizeof(desc)); 150 hfs_dbg(BNODE_MOD, "%d, %d, %d, %d, %d\n", 151 be32_to_cpu(desc.next), be32_to_cpu(desc.prev), 152 desc.type, desc.height, be16_to_cpu(desc.num_recs)); 153 154 off = node->tree->node_size - 2; 155 for (i = be16_to_cpu(desc.num_recs); i >= 0; off -= 2, i--) { 156 key_off = hfs_bnode_read_u16(node, off); 157 hfs_dbg_cont(BNODE_MOD, " %d", key_off); 158 if (i && node->type == HFS_NODE_INDEX) { 159 int tmp; 160 161 if (node->tree->attributes & HFS_TREE_VARIDXKEYS) 162 tmp = (hfs_bnode_read_u8(node, key_off) | 1) + 1; 163 else 164 tmp = node->tree->max_key_len + 1; 165 hfs_dbg_cont(BNODE_MOD, " (%d,%d", 166 tmp, hfs_bnode_read_u8(node, key_off)); 167 hfs_bnode_read(node, &cnid, key_off + tmp, 4); 168 hfs_dbg_cont(BNODE_MOD, ",%d)", be32_to_cpu(cnid)); 169 } else if (i && node->type == HFS_NODE_LEAF) { 170 int tmp; 171 172 tmp = hfs_bnode_read_u8(node, key_off); 173 hfs_dbg_cont(BNODE_MOD, " (%d)", tmp); 174 } 175 } 176 hfs_dbg_cont(BNODE_MOD, "\n"); 177 } 178 179 void hfs_bnode_unlink(struct hfs_bnode *node) 180 { 181 struct hfs_btree *tree; 182 struct hfs_bnode *tmp; 183 __be32 cnid; 184 185 tree = node->tree; 186 if (node->prev) { 187 tmp = hfs_bnode_find(tree, node->prev); 188 if (IS_ERR(tmp)) 189 return; 190 tmp->next = node->next; 191 cnid = cpu_to_be32(tmp->next); 192 hfs_bnode_write(tmp, &cnid, offsetof(struct hfs_bnode_desc, next), 4); 193 hfs_bnode_put(tmp); 194 } else if (node->type == HFS_NODE_LEAF) 195 tree->leaf_head = node->next; 196 197 if (node->next) { 198 tmp = hfs_bnode_find(tree, node->next); 199 if (IS_ERR(tmp)) 200 return; 201 tmp->prev = node->prev; 202 cnid = cpu_to_be32(tmp->prev); 203 hfs_bnode_write(tmp, &cnid, offsetof(struct hfs_bnode_desc, prev), 4); 204 hfs_bnode_put(tmp); 205 } else if (node->type == HFS_NODE_LEAF) 206 tree->leaf_tail = node->prev; 207 208 // move down? 209 if (!node->prev && !node->next) { 210 printk(KERN_DEBUG "hfs_btree_del_level\n"); 211 } 212 if (!node->parent) { 213 tree->root = 0; 214 tree->depth = 0; 215 } 216 set_bit(HFS_BNODE_DELETED, &node->flags); 217 } 218 219 static inline int hfs_bnode_hash(u32 num) 220 { 221 num = (num >> 16) + num; 222 num += num >> 8; 223 return num & (NODE_HASH_SIZE - 1); 224 } 225 226 struct hfs_bnode *hfs_bnode_findhash(struct hfs_btree *tree, u32 cnid) 227 { 228 struct hfs_bnode *node; 229 230 if (cnid >= tree->node_count) { 231 pr_err("request for non-existent node %d in B*Tree\n", cnid); 232 return NULL; 233 } 234 235 for (node = tree->node_hash[hfs_bnode_hash(cnid)]; 236 node; node = node->next_hash) { 237 if (node->this == cnid) { 238 return node; 239 } 240 } 241 return NULL; 242 } 243 244 static struct hfs_bnode *__hfs_bnode_create(struct hfs_btree *tree, u32 cnid) 245 { 246 struct hfs_bnode *node, *node2; 247 struct address_space *mapping; 248 struct page *page; 249 int size, block, i, hash; 250 loff_t off; 251 252 if (cnid >= tree->node_count) { 253 pr_err("request for non-existent node %d in B*Tree\n", cnid); 254 return NULL; 255 } 256 257 size = sizeof(struct hfs_bnode) + tree->pages_per_bnode * 258 sizeof(struct page *); 259 node = kzalloc(size, GFP_KERNEL); 260 if (!node) 261 return NULL; 262 node->tree = tree; 263 node->this = cnid; 264 set_bit(HFS_BNODE_NEW, &node->flags); 265 atomic_set(&node->refcnt, 1); 266 hfs_dbg(BNODE_REFS, "new_node(%d:%d): 1\n", 267 node->tree->cnid, node->this); 268 init_waitqueue_head(&node->lock_wq); 269 spin_lock(&tree->hash_lock); 270 node2 = hfs_bnode_findhash(tree, cnid); 271 if (!node2) { 272 hash = hfs_bnode_hash(cnid); 273 node->next_hash = tree->node_hash[hash]; 274 tree->node_hash[hash] = node; 275 tree->node_hash_cnt++; 276 } else { 277 hfs_bnode_get(node2); 278 spin_unlock(&tree->hash_lock); 279 kfree(node); 280 wait_event(node2->lock_wq, !test_bit(HFS_BNODE_NEW, &node2->flags)); 281 return node2; 282 } 283 spin_unlock(&tree->hash_lock); 284 285 mapping = tree->inode->i_mapping; 286 off = (loff_t)cnid * tree->node_size; 287 block = off >> PAGE_SHIFT; 288 node->page_offset = off & ~PAGE_MASK; 289 for (i = 0; i < tree->pages_per_bnode; i++) { 290 page = read_mapping_page(mapping, block++, NULL); 291 if (IS_ERR(page)) 292 goto fail; 293 node->page[i] = page; 294 } 295 296 return node; 297 fail: 298 set_bit(HFS_BNODE_ERROR, &node->flags); 299 return node; 300 } 301 302 void hfs_bnode_unhash(struct hfs_bnode *node) 303 { 304 struct hfs_bnode **p; 305 306 hfs_dbg(BNODE_REFS, "remove_node(%d:%d): %d\n", 307 node->tree->cnid, node->this, atomic_read(&node->refcnt)); 308 for (p = &node->tree->node_hash[hfs_bnode_hash(node->this)]; 309 *p && *p != node; p = &(*p)->next_hash) 310 ; 311 BUG_ON(!*p); 312 *p = node->next_hash; 313 node->tree->node_hash_cnt--; 314 } 315 316 /* Load a particular node out of a tree */ 317 struct hfs_bnode *hfs_bnode_find(struct hfs_btree *tree, u32 num) 318 { 319 struct hfs_bnode *node; 320 struct hfs_bnode_desc *desc; 321 int i, rec_off, off, next_off; 322 int entry_size, key_size; 323 324 spin_lock(&tree->hash_lock); 325 node = hfs_bnode_findhash(tree, num); 326 if (node) { 327 hfs_bnode_get(node); 328 spin_unlock(&tree->hash_lock); 329 wait_event(node->lock_wq, !test_bit(HFS_BNODE_NEW, &node->flags)); 330 if (test_bit(HFS_BNODE_ERROR, &node->flags)) 331 goto node_error; 332 return node; 333 } 334 spin_unlock(&tree->hash_lock); 335 node = __hfs_bnode_create(tree, num); 336 if (!node) 337 return ERR_PTR(-ENOMEM); 338 if (test_bit(HFS_BNODE_ERROR, &node->flags)) 339 goto node_error; 340 if (!test_bit(HFS_BNODE_NEW, &node->flags)) 341 return node; 342 343 desc = (struct hfs_bnode_desc *)(kmap_local_page(node->page[0]) + 344 node->page_offset); 345 node->prev = be32_to_cpu(desc->prev); 346 node->next = be32_to_cpu(desc->next); 347 node->num_recs = be16_to_cpu(desc->num_recs); 348 node->type = desc->type; 349 node->height = desc->height; 350 kunmap_local(desc); 351 352 switch (node->type) { 353 case HFS_NODE_HEADER: 354 case HFS_NODE_MAP: 355 if (node->height != 0) 356 goto node_error; 357 break; 358 case HFS_NODE_LEAF: 359 if (node->height != 1) 360 goto node_error; 361 break; 362 case HFS_NODE_INDEX: 363 if (node->height <= 1 || node->height > tree->depth) 364 goto node_error; 365 break; 366 default: 367 goto node_error; 368 } 369 370 rec_off = tree->node_size - 2; 371 off = hfs_bnode_read_u16(node, rec_off); 372 if (off != sizeof(struct hfs_bnode_desc)) 373 goto node_error; 374 for (i = 1; i <= node->num_recs; off = next_off, i++) { 375 rec_off -= 2; 376 next_off = hfs_bnode_read_u16(node, rec_off); 377 if (next_off <= off || 378 next_off > tree->node_size || 379 next_off & 1) 380 goto node_error; 381 entry_size = next_off - off; 382 if (node->type != HFS_NODE_INDEX && 383 node->type != HFS_NODE_LEAF) 384 continue; 385 key_size = hfs_bnode_read_u8(node, off) + 1; 386 if (key_size >= entry_size /*|| key_size & 1*/) 387 goto node_error; 388 } 389 clear_bit(HFS_BNODE_NEW, &node->flags); 390 wake_up(&node->lock_wq); 391 return node; 392 393 node_error: 394 set_bit(HFS_BNODE_ERROR, &node->flags); 395 clear_bit(HFS_BNODE_NEW, &node->flags); 396 wake_up(&node->lock_wq); 397 hfs_bnode_put(node); 398 return ERR_PTR(-EIO); 399 } 400 401 void hfs_bnode_free(struct hfs_bnode *node) 402 { 403 int i; 404 405 for (i = 0; i < node->tree->pages_per_bnode; i++) 406 if (node->page[i]) 407 put_page(node->page[i]); 408 kfree(node); 409 } 410 411 struct hfs_bnode *hfs_bnode_create(struct hfs_btree *tree, u32 num) 412 { 413 struct hfs_bnode *node; 414 struct page **pagep; 415 int i; 416 417 spin_lock(&tree->hash_lock); 418 node = hfs_bnode_findhash(tree, num); 419 spin_unlock(&tree->hash_lock); 420 if (node) { 421 pr_crit("new node %u already hashed?\n", num); 422 WARN_ON(1); 423 return node; 424 } 425 node = __hfs_bnode_create(tree, num); 426 if (!node) 427 return ERR_PTR(-ENOMEM); 428 if (test_bit(HFS_BNODE_ERROR, &node->flags)) { 429 hfs_bnode_put(node); 430 return ERR_PTR(-EIO); 431 } 432 433 pagep = node->page; 434 memzero_page(*pagep, node->page_offset, 435 min((int)PAGE_SIZE, (int)tree->node_size)); 436 set_page_dirty(*pagep); 437 for (i = 1; i < tree->pages_per_bnode; i++) { 438 memzero_page(*++pagep, 0, PAGE_SIZE); 439 set_page_dirty(*pagep); 440 } 441 clear_bit(HFS_BNODE_NEW, &node->flags); 442 wake_up(&node->lock_wq); 443 444 return node; 445 } 446 447 void hfs_bnode_get(struct hfs_bnode *node) 448 { 449 if (node) { 450 atomic_inc(&node->refcnt); 451 hfs_dbg(BNODE_REFS, "get_node(%d:%d): %d\n", 452 node->tree->cnid, node->this, 453 atomic_read(&node->refcnt)); 454 } 455 } 456 457 /* Dispose of resources used by a node */ 458 void hfs_bnode_put(struct hfs_bnode *node) 459 { 460 if (node) { 461 struct hfs_btree *tree = node->tree; 462 int i; 463 464 hfs_dbg(BNODE_REFS, "put_node(%d:%d): %d\n", 465 node->tree->cnid, node->this, 466 atomic_read(&node->refcnt)); 467 BUG_ON(!atomic_read(&node->refcnt)); 468 if (!atomic_dec_and_lock(&node->refcnt, &tree->hash_lock)) 469 return; 470 for (i = 0; i < tree->pages_per_bnode; i++) { 471 if (!node->page[i]) 472 continue; 473 mark_page_accessed(node->page[i]); 474 } 475 476 if (test_bit(HFS_BNODE_DELETED, &node->flags)) { 477 hfs_bnode_unhash(node); 478 spin_unlock(&tree->hash_lock); 479 hfs_bmap_free(node); 480 hfs_bnode_free(node); 481 return; 482 } 483 spin_unlock(&tree->hash_lock); 484 } 485 } 486