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(trans, 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(leaf, 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 btrfs_set_key_type(&key, 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 btrfs_set_key_type(&key, 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 btrfs_set_key_type(&key, 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 /* 217 * lookup a directory item based on index. 'dir' is the objectid 218 * we're searching in, and 'mod' tells us if you plan on deleting the 219 * item (use mod < 0) or changing the options (use mod > 0) 220 * 221 * The name is used to make sure the index really points to the name you were 222 * looking for. 223 */ 224 struct btrfs_dir_item * 225 btrfs_lookup_dir_index_item(struct btrfs_trans_handle *trans, 226 struct btrfs_root *root, 227 struct btrfs_path *path, u64 dir, 228 u64 objectid, const char *name, int name_len, 229 int mod) 230 { 231 int ret; 232 struct btrfs_key key; 233 int ins_len = mod < 0 ? -1 : 0; 234 int cow = mod != 0; 235 236 key.objectid = dir; 237 btrfs_set_key_type(&key, BTRFS_DIR_INDEX_KEY); 238 key.offset = objectid; 239 240 ret = btrfs_search_slot(trans, root, &key, path, ins_len, cow); 241 if (ret < 0) 242 return ERR_PTR(ret); 243 if (ret > 0) 244 return ERR_PTR(-ENOENT); 245 return btrfs_match_dir_item_name(root, path, name, name_len); 246 } 247 248 struct btrfs_dir_item * 249 btrfs_search_dir_index_item(struct btrfs_root *root, 250 struct btrfs_path *path, u64 dirid, 251 const char *name, int name_len) 252 { 253 struct extent_buffer *leaf; 254 struct btrfs_dir_item *di; 255 struct btrfs_key key; 256 u32 nritems; 257 int ret; 258 259 key.objectid = dirid; 260 key.type = BTRFS_DIR_INDEX_KEY; 261 key.offset = 0; 262 263 ret = btrfs_search_slot(NULL, root, &key, path, 0, 0); 264 if (ret < 0) 265 return ERR_PTR(ret); 266 267 leaf = path->nodes[0]; 268 nritems = btrfs_header_nritems(leaf); 269 270 while (1) { 271 if (path->slots[0] >= nritems) { 272 ret = btrfs_next_leaf(root, path); 273 if (ret < 0) 274 return ERR_PTR(ret); 275 if (ret > 0) 276 break; 277 leaf = path->nodes[0]; 278 nritems = btrfs_header_nritems(leaf); 279 continue; 280 } 281 282 btrfs_item_key_to_cpu(leaf, &key, path->slots[0]); 283 if (key.objectid != dirid || key.type != BTRFS_DIR_INDEX_KEY) 284 break; 285 286 di = btrfs_match_dir_item_name(root, path, name, name_len); 287 if (di) 288 return di; 289 290 path->slots[0]++; 291 } 292 return NULL; 293 } 294 295 struct btrfs_dir_item *btrfs_lookup_xattr(struct btrfs_trans_handle *trans, 296 struct btrfs_root *root, 297 struct btrfs_path *path, u64 dir, 298 const char *name, u16 name_len, 299 int mod) 300 { 301 int ret; 302 struct btrfs_key key; 303 int ins_len = mod < 0 ? -1 : 0; 304 int cow = mod != 0; 305 306 key.objectid = dir; 307 btrfs_set_key_type(&key, BTRFS_XATTR_ITEM_KEY); 308 key.offset = btrfs_name_hash(name, name_len); 309 ret = btrfs_search_slot(trans, root, &key, path, ins_len, cow); 310 if (ret < 0) 311 return ERR_PTR(ret); 312 if (ret > 0) 313 return NULL; 314 315 return btrfs_match_dir_item_name(root, path, name, name_len); 316 } 317 318 /* 319 * helper function to look at the directory item pointed to by 'path' 320 * this walks through all the entries in a dir item and finds one 321 * for a specific name. 322 */ 323 struct btrfs_dir_item *btrfs_match_dir_item_name(struct btrfs_root *root, 324 struct btrfs_path *path, 325 const char *name, int name_len) 326 { 327 struct btrfs_dir_item *dir_item; 328 unsigned long name_ptr; 329 u32 total_len; 330 u32 cur = 0; 331 u32 this_len; 332 struct extent_buffer *leaf; 333 334 leaf = path->nodes[0]; 335 dir_item = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_dir_item); 336 if (verify_dir_item(root, leaf, dir_item)) 337 return NULL; 338 339 total_len = btrfs_item_size_nr(leaf, path->slots[0]); 340 while (cur < total_len) { 341 this_len = sizeof(*dir_item) + 342 btrfs_dir_name_len(leaf, dir_item) + 343 btrfs_dir_data_len(leaf, dir_item); 344 name_ptr = (unsigned long)(dir_item + 1); 345 346 if (btrfs_dir_name_len(leaf, dir_item) == name_len && 347 memcmp_extent_buffer(leaf, name, name_ptr, name_len) == 0) 348 return dir_item; 349 350 cur += this_len; 351 dir_item = (struct btrfs_dir_item *)((char *)dir_item + 352 this_len); 353 } 354 return NULL; 355 } 356 357 /* 358 * given a pointer into a directory item, delete it. This 359 * handles items that have more than one entry in them. 360 */ 361 int btrfs_delete_one_dir_name(struct btrfs_trans_handle *trans, 362 struct btrfs_root *root, 363 struct btrfs_path *path, 364 struct btrfs_dir_item *di) 365 { 366 367 struct extent_buffer *leaf; 368 u32 sub_item_len; 369 u32 item_len; 370 int ret = 0; 371 372 leaf = path->nodes[0]; 373 sub_item_len = sizeof(*di) + btrfs_dir_name_len(leaf, di) + 374 btrfs_dir_data_len(leaf, di); 375 item_len = btrfs_item_size_nr(leaf, path->slots[0]); 376 if (sub_item_len == item_len) { 377 ret = btrfs_del_item(trans, root, path); 378 } else { 379 /* MARKER */ 380 unsigned long ptr = (unsigned long)di; 381 unsigned long start; 382 383 start = btrfs_item_ptr_offset(leaf, path->slots[0]); 384 memmove_extent_buffer(leaf, ptr, ptr + sub_item_len, 385 item_len - (ptr + sub_item_len - start)); 386 btrfs_truncate_item(trans, root, path, 387 item_len - sub_item_len, 1); 388 } 389 return ret; 390 } 391 392 int verify_dir_item(struct btrfs_root *root, 393 struct extent_buffer *leaf, 394 struct btrfs_dir_item *dir_item) 395 { 396 u16 namelen = BTRFS_NAME_LEN; 397 u8 type = btrfs_dir_type(leaf, dir_item); 398 399 if (type >= BTRFS_FT_MAX) { 400 printk(KERN_CRIT "btrfs: invalid dir item type: %d\n", 401 (int)type); 402 return 1; 403 } 404 405 if (type == BTRFS_FT_XATTR) 406 namelen = XATTR_NAME_MAX; 407 408 if (btrfs_dir_name_len(leaf, dir_item) > namelen) { 409 printk(KERN_CRIT "btrfs: invalid dir item name len: %u\n", 410 (unsigned)btrfs_dir_data_len(leaf, dir_item)); 411 return 1; 412 } 413 414 /* BTRFS_MAX_XATTR_SIZE is the same for all dir items */ 415 if (btrfs_dir_data_len(leaf, dir_item) > BTRFS_MAX_XATTR_SIZE(root)) { 416 printk(KERN_CRIT "btrfs: invalid dir item data len: %u\n", 417 (unsigned)btrfs_dir_data_len(leaf, dir_item)); 418 return 1; 419 } 420 421 return 0; 422 } 423