1 /* 2 * Copyright (C) 2007 Oracle. All rights reserved. 3 * 4 * This program is free software; you can redistribute it and/or 5 * modify it under the terms of the GNU General Public 6 * License v2 as published by the Free Software Foundation. 7 * 8 * This program is distributed in the hope that it will be useful, 9 * but WITHOUT ANY WARRANTY; without even the implied warranty of 10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 11 * General Public License for more details. 12 * 13 * You should have received a copy of the GNU General Public 14 * License along with this program; if not, write to the 15 * Free Software Foundation, Inc., 59 Temple Place - Suite 330, 16 * Boston, MA 021110-1307, USA. 17 */ 18 19 #include "ctree.h" 20 #include "disk-io.h" 21 #include "hash.h" 22 #include "transaction.h" 23 24 static struct btrfs_dir_item *btrfs_match_dir_item_name(struct btrfs_root *root, 25 struct btrfs_path *path, 26 const char *name, int name_len); 27 28 /* 29 * insert a name into a directory, doing overflow properly if there is a hash 30 * collision. data_size indicates how big the item inserted should be. On 31 * success a struct btrfs_dir_item pointer is returned, otherwise it is 32 * an ERR_PTR. 33 * 34 * The name is not copied into the dir item, you have to do that yourself. 35 */ 36 static struct btrfs_dir_item *insert_with_overflow(struct btrfs_trans_handle 37 *trans, 38 struct btrfs_root *root, 39 struct btrfs_path *path, 40 struct btrfs_key *cpu_key, 41 u32 data_size, 42 const char *name, 43 int name_len) 44 { 45 int ret; 46 char *ptr; 47 struct btrfs_item *item; 48 struct extent_buffer *leaf; 49 50 ret = btrfs_insert_empty_item(trans, root, path, cpu_key, data_size); 51 if (ret == -EEXIST) { 52 struct btrfs_dir_item *di; 53 di = btrfs_match_dir_item_name(root, path, name, name_len); 54 if (di) 55 return ERR_PTR(-EEXIST); 56 btrfs_extend_item(root, path, data_size); 57 } else if (ret < 0) 58 return ERR_PTR(ret); 59 WARN_ON(ret > 0); 60 leaf = path->nodes[0]; 61 item = btrfs_item_nr(leaf, path->slots[0]); 62 ptr = btrfs_item_ptr(leaf, path->slots[0], char); 63 BUG_ON(data_size > btrfs_item_size(leaf, item)); 64 ptr += btrfs_item_size(leaf, item) - data_size; 65 return (struct btrfs_dir_item *)ptr; 66 } 67 68 /* 69 * xattrs work a lot like directories, this inserts an xattr item 70 * into the tree 71 */ 72 int btrfs_insert_xattr_item(struct btrfs_trans_handle *trans, 73 struct btrfs_root *root, 74 struct btrfs_path *path, u64 objectid, 75 const char *name, u16 name_len, 76 const void *data, u16 data_len) 77 { 78 int ret = 0; 79 struct btrfs_dir_item *dir_item; 80 unsigned long name_ptr, data_ptr; 81 struct btrfs_key key, location; 82 struct btrfs_disk_key disk_key; 83 struct extent_buffer *leaf; 84 u32 data_size; 85 86 BUG_ON(name_len + data_len > BTRFS_MAX_XATTR_SIZE(root)); 87 88 key.objectid = objectid; 89 btrfs_set_key_type(&key, BTRFS_XATTR_ITEM_KEY); 90 key.offset = btrfs_name_hash(name, name_len); 91 92 data_size = sizeof(*dir_item) + name_len + data_len; 93 dir_item = insert_with_overflow(trans, root, path, &key, data_size, 94 name, name_len); 95 if (IS_ERR(dir_item)) 96 return PTR_ERR(dir_item); 97 memset(&location, 0, sizeof(location)); 98 99 leaf = path->nodes[0]; 100 btrfs_cpu_key_to_disk(&disk_key, &location); 101 btrfs_set_dir_item_key(leaf, dir_item, &disk_key); 102 btrfs_set_dir_type(leaf, dir_item, BTRFS_FT_XATTR); 103 btrfs_set_dir_name_len(leaf, dir_item, name_len); 104 btrfs_set_dir_transid(leaf, dir_item, trans->transid); 105 btrfs_set_dir_data_len(leaf, dir_item, data_len); 106 name_ptr = (unsigned long)(dir_item + 1); 107 data_ptr = (unsigned long)((char *)name_ptr + name_len); 108 109 write_extent_buffer(leaf, name, name_ptr, name_len); 110 write_extent_buffer(leaf, data, data_ptr, data_len); 111 btrfs_mark_buffer_dirty(path->nodes[0]); 112 113 return ret; 114 } 115 116 /* 117 * insert a directory item in the tree, doing all the magic for 118 * both indexes. 'dir' indicates which objectid to insert it into, 119 * 'location' is the key to stuff into the directory item, 'type' is the 120 * type of the inode we're pointing to, and 'index' is the sequence number 121 * to use for the second index (if one is created). 122 * Will return 0 or -ENOMEM 123 */ 124 int btrfs_insert_dir_item(struct btrfs_trans_handle *trans, struct btrfs_root 125 *root, const char *name, int name_len, 126 struct inode *dir, struct btrfs_key *location, 127 u8 type, u64 index) 128 { 129 int ret = 0; 130 int ret2 = 0; 131 struct btrfs_path *path; 132 struct btrfs_dir_item *dir_item; 133 struct extent_buffer *leaf; 134 unsigned long name_ptr; 135 struct btrfs_key key; 136 struct btrfs_disk_key disk_key; 137 u32 data_size; 138 139 key.objectid = btrfs_ino(dir); 140 btrfs_set_key_type(&key, BTRFS_DIR_ITEM_KEY); 141 key.offset = btrfs_name_hash(name, name_len); 142 143 path = btrfs_alloc_path(); 144 if (!path) 145 return -ENOMEM; 146 path->leave_spinning = 1; 147 148 btrfs_cpu_key_to_disk(&disk_key, location); 149 150 data_size = sizeof(*dir_item) + name_len; 151 dir_item = insert_with_overflow(trans, root, path, &key, data_size, 152 name, name_len); 153 if (IS_ERR(dir_item)) { 154 ret = PTR_ERR(dir_item); 155 if (ret == -EEXIST) 156 goto second_insert; 157 goto out_free; 158 } 159 160 leaf = path->nodes[0]; 161 btrfs_set_dir_item_key(leaf, dir_item, &disk_key); 162 btrfs_set_dir_type(leaf, dir_item, type); 163 btrfs_set_dir_data_len(leaf, dir_item, 0); 164 btrfs_set_dir_name_len(leaf, dir_item, name_len); 165 btrfs_set_dir_transid(leaf, dir_item, trans->transid); 166 name_ptr = (unsigned long)(dir_item + 1); 167 168 write_extent_buffer(leaf, name, name_ptr, name_len); 169 btrfs_mark_buffer_dirty(leaf); 170 171 second_insert: 172 /* FIXME, use some real flag for selecting the extra index */ 173 if (root == root->fs_info->tree_root) { 174 ret = 0; 175 goto out_free; 176 } 177 btrfs_release_path(path); 178 179 ret2 = btrfs_insert_delayed_dir_index(trans, root, name, name_len, dir, 180 &disk_key, type, index); 181 out_free: 182 btrfs_free_path(path); 183 if (ret) 184 return ret; 185 if (ret2) 186 return ret2; 187 return 0; 188 } 189 190 /* 191 * lookup a directory item based on name. 'dir' is the objectid 192 * we're searching in, and 'mod' tells us if you plan on deleting the 193 * item (use mod < 0) or changing the options (use mod > 0) 194 */ 195 struct btrfs_dir_item *btrfs_lookup_dir_item(struct btrfs_trans_handle *trans, 196 struct btrfs_root *root, 197 struct btrfs_path *path, u64 dir, 198 const char *name, int name_len, 199 int mod) 200 { 201 int ret; 202 struct btrfs_key key; 203 int ins_len = mod < 0 ? -1 : 0; 204 int cow = mod != 0; 205 206 key.objectid = dir; 207 btrfs_set_key_type(&key, BTRFS_DIR_ITEM_KEY); 208 209 key.offset = btrfs_name_hash(name, name_len); 210 211 ret = btrfs_search_slot(trans, root, &key, path, ins_len, cow); 212 if (ret < 0) 213 return ERR_PTR(ret); 214 if (ret > 0) 215 return NULL; 216 217 return btrfs_match_dir_item_name(root, path, name, name_len); 218 } 219 220 int btrfs_check_dir_item_collision(struct btrfs_root *root, u64 dir, 221 const char *name, int name_len) 222 { 223 int ret; 224 struct btrfs_key key; 225 struct btrfs_dir_item *di; 226 int data_size; 227 struct extent_buffer *leaf; 228 int slot; 229 struct btrfs_path *path; 230 231 232 path = btrfs_alloc_path(); 233 if (!path) 234 return -ENOMEM; 235 236 key.objectid = dir; 237 btrfs_set_key_type(&key, BTRFS_DIR_ITEM_KEY); 238 key.offset = btrfs_name_hash(name, name_len); 239 240 ret = btrfs_search_slot(NULL, root, &key, path, 0, 0); 241 242 /* return back any errors */ 243 if (ret < 0) 244 goto out; 245 246 /* nothing found, we're safe */ 247 if (ret > 0) { 248 ret = 0; 249 goto out; 250 } 251 252 /* we found an item, look for our name in the item */ 253 di = btrfs_match_dir_item_name(root, path, name, name_len); 254 if (di) { 255 /* our exact name was found */ 256 ret = -EEXIST; 257 goto out; 258 } 259 260 /* 261 * see if there is room in the item to insert this 262 * name 263 */ 264 data_size = sizeof(*di) + name_len + sizeof(struct btrfs_item); 265 leaf = path->nodes[0]; 266 slot = path->slots[0]; 267 if (data_size + btrfs_item_size_nr(leaf, slot) + 268 sizeof(struct btrfs_item) > BTRFS_LEAF_DATA_SIZE(root)) { 269 ret = -EOVERFLOW; 270 } else { 271 /* plenty of insertion room */ 272 ret = 0; 273 } 274 out: 275 btrfs_free_path(path); 276 return ret; 277 } 278 279 /* 280 * lookup a directory item based on index. 'dir' is the objectid 281 * we're searching in, and 'mod' tells us if you plan on deleting the 282 * item (use mod < 0) or changing the options (use mod > 0) 283 * 284 * The name is used to make sure the index really points to the name you were 285 * looking for. 286 */ 287 struct btrfs_dir_item * 288 btrfs_lookup_dir_index_item(struct btrfs_trans_handle *trans, 289 struct btrfs_root *root, 290 struct btrfs_path *path, u64 dir, 291 u64 objectid, const char *name, int name_len, 292 int mod) 293 { 294 int ret; 295 struct btrfs_key key; 296 int ins_len = mod < 0 ? -1 : 0; 297 int cow = mod != 0; 298 299 key.objectid = dir; 300 btrfs_set_key_type(&key, BTRFS_DIR_INDEX_KEY); 301 key.offset = objectid; 302 303 ret = btrfs_search_slot(trans, root, &key, path, ins_len, cow); 304 if (ret < 0) 305 return ERR_PTR(ret); 306 if (ret > 0) 307 return ERR_PTR(-ENOENT); 308 return btrfs_match_dir_item_name(root, path, name, name_len); 309 } 310 311 struct btrfs_dir_item * 312 btrfs_search_dir_index_item(struct btrfs_root *root, 313 struct btrfs_path *path, u64 dirid, 314 const char *name, int name_len) 315 { 316 struct extent_buffer *leaf; 317 struct btrfs_dir_item *di; 318 struct btrfs_key key; 319 u32 nritems; 320 int ret; 321 322 key.objectid = dirid; 323 key.type = BTRFS_DIR_INDEX_KEY; 324 key.offset = 0; 325 326 ret = btrfs_search_slot(NULL, root, &key, path, 0, 0); 327 if (ret < 0) 328 return ERR_PTR(ret); 329 330 leaf = path->nodes[0]; 331 nritems = btrfs_header_nritems(leaf); 332 333 while (1) { 334 if (path->slots[0] >= nritems) { 335 ret = btrfs_next_leaf(root, path); 336 if (ret < 0) 337 return ERR_PTR(ret); 338 if (ret > 0) 339 break; 340 leaf = path->nodes[0]; 341 nritems = btrfs_header_nritems(leaf); 342 continue; 343 } 344 345 btrfs_item_key_to_cpu(leaf, &key, path->slots[0]); 346 if (key.objectid != dirid || key.type != BTRFS_DIR_INDEX_KEY) 347 break; 348 349 di = btrfs_match_dir_item_name(root, path, name, name_len); 350 if (di) 351 return di; 352 353 path->slots[0]++; 354 } 355 return NULL; 356 } 357 358 struct btrfs_dir_item *btrfs_lookup_xattr(struct btrfs_trans_handle *trans, 359 struct btrfs_root *root, 360 struct btrfs_path *path, u64 dir, 361 const char *name, u16 name_len, 362 int mod) 363 { 364 int ret; 365 struct btrfs_key key; 366 int ins_len = mod < 0 ? -1 : 0; 367 int cow = mod != 0; 368 369 key.objectid = dir; 370 btrfs_set_key_type(&key, BTRFS_XATTR_ITEM_KEY); 371 key.offset = btrfs_name_hash(name, name_len); 372 ret = btrfs_search_slot(trans, root, &key, path, ins_len, cow); 373 if (ret < 0) 374 return ERR_PTR(ret); 375 if (ret > 0) 376 return NULL; 377 378 return btrfs_match_dir_item_name(root, path, name, name_len); 379 } 380 381 /* 382 * helper function to look at the directory item pointed to by 'path' 383 * this walks through all the entries in a dir item and finds one 384 * for a specific name. 385 */ 386 static struct btrfs_dir_item *btrfs_match_dir_item_name(struct btrfs_root *root, 387 struct btrfs_path *path, 388 const char *name, int name_len) 389 { 390 struct btrfs_dir_item *dir_item; 391 unsigned long name_ptr; 392 u32 total_len; 393 u32 cur = 0; 394 u32 this_len; 395 struct extent_buffer *leaf; 396 397 leaf = path->nodes[0]; 398 dir_item = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_dir_item); 399 if (verify_dir_item(root, leaf, dir_item)) 400 return NULL; 401 402 total_len = btrfs_item_size_nr(leaf, path->slots[0]); 403 while (cur < total_len) { 404 this_len = sizeof(*dir_item) + 405 btrfs_dir_name_len(leaf, dir_item) + 406 btrfs_dir_data_len(leaf, dir_item); 407 name_ptr = (unsigned long)(dir_item + 1); 408 409 if (btrfs_dir_name_len(leaf, dir_item) == name_len && 410 memcmp_extent_buffer(leaf, name, name_ptr, name_len) == 0) 411 return dir_item; 412 413 cur += this_len; 414 dir_item = (struct btrfs_dir_item *)((char *)dir_item + 415 this_len); 416 } 417 return NULL; 418 } 419 420 /* 421 * given a pointer into a directory item, delete it. This 422 * handles items that have more than one entry in them. 423 */ 424 int btrfs_delete_one_dir_name(struct btrfs_trans_handle *trans, 425 struct btrfs_root *root, 426 struct btrfs_path *path, 427 struct btrfs_dir_item *di) 428 { 429 430 struct extent_buffer *leaf; 431 u32 sub_item_len; 432 u32 item_len; 433 int ret = 0; 434 435 leaf = path->nodes[0]; 436 sub_item_len = sizeof(*di) + btrfs_dir_name_len(leaf, di) + 437 btrfs_dir_data_len(leaf, di); 438 item_len = btrfs_item_size_nr(leaf, path->slots[0]); 439 if (sub_item_len == item_len) { 440 ret = btrfs_del_item(trans, root, path); 441 } else { 442 /* MARKER */ 443 unsigned long ptr = (unsigned long)di; 444 unsigned long start; 445 446 start = btrfs_item_ptr_offset(leaf, path->slots[0]); 447 memmove_extent_buffer(leaf, ptr, ptr + sub_item_len, 448 item_len - (ptr + sub_item_len - start)); 449 btrfs_truncate_item(root, path, item_len - sub_item_len, 1); 450 } 451 return ret; 452 } 453 454 int verify_dir_item(struct btrfs_root *root, 455 struct extent_buffer *leaf, 456 struct btrfs_dir_item *dir_item) 457 { 458 u16 namelen = BTRFS_NAME_LEN; 459 u8 type = btrfs_dir_type(leaf, dir_item); 460 461 if (type >= BTRFS_FT_MAX) { 462 printk(KERN_CRIT "btrfs: invalid dir item type: %d\n", 463 (int)type); 464 return 1; 465 } 466 467 if (type == BTRFS_FT_XATTR) 468 namelen = XATTR_NAME_MAX; 469 470 if (btrfs_dir_name_len(leaf, dir_item) > namelen) { 471 printk(KERN_CRIT "btrfs: invalid dir item name len: %u\n", 472 (unsigned)btrfs_dir_data_len(leaf, dir_item)); 473 return 1; 474 } 475 476 /* BTRFS_MAX_XATTR_SIZE is the same for all dir items */ 477 if (btrfs_dir_data_len(leaf, dir_item) > BTRFS_MAX_XATTR_SIZE(root)) { 478 printk(KERN_CRIT "btrfs: invalid dir item data len: %u\n", 479 (unsigned)btrfs_dir_data_len(leaf, dir_item)); 480 return 1; 481 } 482 483 return 0; 484 } 485