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