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