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