fs/nfs/blocklayout/extents.c

   1 /*
   2  *  linux/fs/nfs/blocklayout/blocklayout.h
   3  *
   4  *  Module for the NFSv4.1 pNFS block layout driver.
   5  *
   6  *  Copyright (c) 2006 The Regents of the University of Michigan.
   7  *  All rights reserved.
   8  *
   9  *  Andy Adamson <andros@citi.umich.edu>
  10  *  Fred Isaman <iisaman@umich.edu>
  11  *
  12  * permission is granted to use, copy, create derivative works and
  13  * redistribute this software and such derivative works for any purpose,
  14  * so long as the name of the university of michigan is not used in
  15  * any advertising or publicity pertaining to the use or distribution
  16  * of this software without specific, written prior authorization.  if
  17  * the above copyright notice or any other identification of the
  18  * university of michigan is included in any copy of any portion of
  19  * this software, then the disclaimer below must also be included.
  20  *
  21  * this software is provided as is, without representation from the
  22  * university of michigan as to its fitness for any purpose, and without
  23  * warranty by the university of michigan of any kind, either express
  24  * or implied, including without limitation the implied warranties of
  25  * merchantability and fitness for a particular purpose.  the regents
  26  * of the university of michigan shall not be liable for any damages,
  27  * including special, indirect, incidental, or consequential damages,
  28  * with respect to any claim arising out or in connection with the use
  29  * of the software, even if it has been or is hereafter advised of the
  30  * possibility of such damages.
  31  */
  32
  33 #include "blocklayout.h"
  34 #define NFSDBG_FACILITY         NFSDBG_PNFS_LD
  35
  36 /* Bit numbers */
  37 #define EXTENT_INITIALIZED 0
  38 #define EXTENT_WRITTEN     1
  39 #define EXTENT_IN_COMMIT   2
  40 #define INTERNAL_EXISTS    MY_MAX_TAGS
  41 #define INTERNAL_MASK      ((1 << INTERNAL_EXISTS) - 1)
  42
  43 /* Returns largest t<=s s.t. t%base==0 */
  44 static inline sector_t normalize(sector_t s, int base)
  45 {
  46         sector_t tmp = s; /* Since do_div modifies its argument */
  47         return s - do_div(tmp, base);
  48 }
  49
  50 static inline sector_t normalize_up(sector_t s, int base)
  51 {
  52         return normalize(s + base - 1, base);
  53 }
  54
  55 /* Complete stub using list while determine API wanted */
  56
  57 /* Returns tags, or negative */
  58 static int32_t _find_entry(struct my_tree *tree, u64 s)
  59 {
  60         struct pnfs_inval_tracking *pos;
  61
  62         dprintk("%s(%llu) enter\n", __func__, s);
  63         list_for_each_entry_reverse(pos, &tree->mtt_stub, it_link) {
  64                 if (pos->it_sector > s)
  65                         continue;
  66                 else if (pos->it_sector == s)
  67                         return pos->it_tags & INTERNAL_MASK;
  68                 else
  69                         break;
  70         }
  71         return -ENOENT;
  72 }
  73
  74 static inline
  75 int _has_tag(struct my_tree *tree, u64 s, int32_t tag)
  76 {
  77         int32_t tags;
  78
  79         dprintk("%s(%llu, %i) enter\n", __func__, s, tag);
  80         s = normalize(s, tree->mtt_step_size);
  81         tags = _find_entry(tree, s);
  82         if ((tags < 0) || !(tags & (1 << tag)))
  83                 return 0;
  84         else
  85                 return 1;
  86 }
  87
  88 /* Creates entry with tag, or if entry already exists, unions tag to it.
  89  * If storage is not NULL, newly created entry will use it.
  90  * Returns number of entries added, or negative on error.
  91  */
  92 static int _add_entry(struct my_tree *tree, u64 s, int32_t tag,
  93                       struct pnfs_inval_tracking *storage)
  94 {
  95         int found = 0;
  96         struct pnfs_inval_tracking *pos;
  97
  98         dprintk("%s(%llu, %i, %p) enter\n", __func__, s, tag, storage);
  99         list_for_each_entry_reverse(pos, &tree->mtt_stub, it_link) {
 100                 if (pos->it_sector > s)
 101                         continue;
 102                 else if (pos->it_sector == s) {
 103                         found = 1;
 104                         break;
 105                 } else
 106                         break;
 107         }
 108         if (found) {
 109                 pos->it_tags |= (1 << tag);
 110                 return 0;
 111         } else {
 112                 struct pnfs_inval_tracking *new;
 113                 if (storage)
 114                         new = storage;
 115                 else {
 116                         new = kmalloc(sizeof(*new), GFP_NOFS);
 117                         if (!new)
 118                                 return -ENOMEM;
 119                 }
 120                 new->it_sector = s;
 121                 new->it_tags = (1 << tag);
 122                 list_add(&new->it_link, &pos->it_link);
 123                 return 1;
 124         }
 125 }
 126
 127 /* XXXX Really want option to not create */
 128 /* Over range, unions tag with existing entries, else creates entry with tag */
 129 static int _set_range(struct my_tree *tree, int32_t tag, u64 s, u64 length)
 130 {
 131         u64 i;
 132
 133         dprintk("%s(%i, %llu, %llu) enter\n", __func__, tag, s, length);
 134         for (i = normalize(s, tree->mtt_step_size); i < s + length;
 135              i += tree->mtt_step_size)
 136                 if (_add_entry(tree, i, tag, NULL))
 137                         return -ENOMEM;
 138         return 0;
 139 }
 140
 141 /* Ensure that future operations on given range of tree will not malloc */
 142 static int _preload_range(struct my_tree *tree, u64 offset, u64 length)
 143 {
 144         u64 start, end, s;
 145         int count, i, used = 0, status = -ENOMEM;
 146         struct pnfs_inval_tracking **storage;
 147
 148         dprintk("%s(%llu, %llu) enter\n", __func__, offset, length);
 149         start = normalize(offset, tree->mtt_step_size);
 150         end = normalize_up(offset + length, tree->mtt_step_size);
 151         count = (int)(end - start) / (int)tree->mtt_step_size;
 152
 153         /* Pre-malloc what memory we might need */
 154         storage = kmalloc(sizeof(*storage) * count, GFP_NOFS);
 155         if (!storage)
 156                 return -ENOMEM;
 157         for (i = 0; i < count; i++) {
 158                 storage[i] = kmalloc(sizeof(struct pnfs_inval_tracking),
 159                                      GFP_NOFS);
 160                 if (!storage[i])
 161                         goto out_cleanup;
 162         }
 163
 164         /* Now need lock - HOW??? */
 165
 166         for (s = start; s < end; s += tree->mtt_step_size)
 167                 used += _add_entry(tree, s, INTERNAL_EXISTS, storage[used]);
 168
 169         /* Unlock - HOW??? */
 170         status = 0;
 171
 172  out_cleanup:
 173         for (i = used; i < count; i++) {
 174                 if (!storage[i])
 175                         break;
 176                 kfree(storage[i]);
 177         }
 178         kfree(storage);
 179         return status;
 180 }
 181
 182 static void set_needs_init(sector_t *array, sector_t offset)
 183 {
 184         sector_t *p = array;
 185
 186         dprintk("%s enter\n", __func__);
 187         if (!p)
 188                 return;
 189         while (*p < offset)
 190                 p++;
 191         if (*p == offset)
 192                 return;
 193         else if (*p == ~0) {
 194                 *p++ = offset;
 195                 *p = ~0;
 196                 return;
 197         } else {
 198                 sector_t *save = p;
 199                 dprintk("%s Adding %llu\n", __func__, (u64)offset);
 200                 while (*p != ~0)
 201                         p++;
 202                 p++;
 203                 memmove(save + 1, save, (char *)p - (char *)save);
 204                 *save = offset;
 205                 return;
 206         }
 207 }
 208
 209 /* We are relying on page lock to serialize this */
 210 int bl_is_sector_init(struct pnfs_inval_markings *marks, sector_t isect)
 211 {
 212         int rv;
 213
 214         spin_lock(&marks->im_lock);
 215         rv = _has_tag(&marks->im_tree, isect, EXTENT_INITIALIZED);
 216         spin_unlock(&marks->im_lock);
 217         return rv;
 218 }
 219
 220 /* Marks sectors in [offest, offset_length) as having been initialized.
 221  * All lengths are step-aligned, where step is min(pagesize, blocksize).
 222  * Notes where partial block is initialized, and helps prepare it for
 223  * complete initialization later.
 224  */
 225 /* Currently assumes offset is page-aligned */
 226 int bl_mark_sectors_init(struct pnfs_inval_markings *marks,
 227                              sector_t offset, sector_t length,
 228                              sector_t **pages)
 229 {
 230         sector_t s, start, end;
 231         sector_t *array = NULL; /* Pages to mark */
 232
 233         dprintk("%s(offset=%llu,len=%llu) enter\n",
 234                 __func__, (u64)offset, (u64)length);
 235         s = max((sector_t) 3,
 236                 2 * (marks->im_block_size / (PAGE_CACHE_SECTORS)));
 237         dprintk("%s set max=%llu\n", __func__, (u64)s);
 238         if (pages) {
 239                 array = kmalloc(s * sizeof(sector_t), GFP_NOFS);
 240                 if (!array)
 241                         goto outerr;
 242                 array[0] = ~0;
 243         }
 244
 245         start = normalize(offset, marks->im_block_size);
 246         end = normalize_up(offset + length, marks->im_block_size);
 247         if (_preload_range(&marks->im_tree, start, end - start))
 248                 goto outerr;
 249
 250         spin_lock(&marks->im_lock);
 251
 252         for (s = normalize_up(start, PAGE_CACHE_SECTORS);
 253              s < offset; s += PAGE_CACHE_SECTORS) {
 254                 dprintk("%s pre-area pages\n", __func__);
 255                 /* Portion of used block is not initialized */
 256                 if (!_has_tag(&marks->im_tree, s, EXTENT_INITIALIZED))
 257                         set_needs_init(array, s);
 258         }
 259         if (_set_range(&marks->im_tree, EXTENT_INITIALIZED, offset, length))
 260                 goto out_unlock;
 261         for (s = normalize_up(offset + length, PAGE_CACHE_SECTORS);
 262              s < end; s += PAGE_CACHE_SECTORS) {
 263                 dprintk("%s post-area pages\n", __func__);
 264                 if (!_has_tag(&marks->im_tree, s, EXTENT_INITIALIZED))
 265                         set_needs_init(array, s);
 266         }
 267
 268         spin_unlock(&marks->im_lock);
 269
 270         if (pages) {
 271                 if (array[0] == ~0) {
 272                         kfree(array);
 273                         *pages = NULL;
 274                 } else
 275                         *pages = array;
 276         }
 277         return 0;
 278
 279  out_unlock:
 280         spin_unlock(&marks->im_lock);
 281  outerr:
 282         if (pages) {
 283                 kfree(array);
 284                 *pages = NULL;
 285         }
 286         return -ENOMEM;
 287 }
 288
 289 static void print_bl_extent(struct pnfs_block_extent *be)
 290 {
 291         dprintk("PRINT EXTENT extent %p\n", be);
 292         if (be) {
 293                 dprintk("        be_f_offset %llu\n", (u64)be->be_f_offset);
 294                 dprintk("        be_length   %llu\n", (u64)be->be_length);
 295                 dprintk("        be_v_offset %llu\n", (u64)be->be_v_offset);
 296                 dprintk("        be_state    %d\n", be->be_state);
 297         }
 298 }
 299
 300 static void
 301 destroy_extent(struct kref *kref)
 302 {
 303         struct pnfs_block_extent *be;
 304
 305         be = container_of(kref, struct pnfs_block_extent, be_refcnt);
 306         dprintk("%s be=%p\n", __func__, be);
 307         kfree(be);
 308 }
 309
 310 void
 311 bl_put_extent(struct pnfs_block_extent *be)
 312 {
 313         if (be) {
 314                 dprintk("%s enter %p (%i)\n", __func__, be,
 315                         atomic_read(&be->be_refcnt.refcount));
 316                 kref_put(&be->be_refcnt, destroy_extent);
 317         }
 318 }
 319
 320 struct pnfs_block_extent *bl_alloc_extent(void)
 321 {
 322         struct pnfs_block_extent *be;
 323
 324         be = kmalloc(sizeof(struct pnfs_block_extent), GFP_NOFS);
 325         if (!be)
 326                 return NULL;
 327         INIT_LIST_HEAD(&be->be_node);
 328         kref_init(&be->be_refcnt);
 329         be->be_inval = NULL;
 330         return be;
 331 }
 332
 333 static void print_elist(struct list_head *list)
 334 {
 335         struct pnfs_block_extent *be;
 336         dprintk("****************\n");
 337         dprintk("Extent list looks like:\n");
 338         list_for_each_entry(be, list, be_node) {
 339                 print_bl_extent(be);
 340         }
 341         dprintk("****************\n");
 342 }
 343
 344 static inline int
 345 extents_consistent(struct pnfs_block_extent *old, struct pnfs_block_extent *new)
 346 {
 347         /* Note this assumes new->be_f_offset >= old->be_f_offset */
 348         return (new->be_state == old->be_state) &&
 349                 ((new->be_state == PNFS_BLOCK_NONE_DATA) ||
 350                  ((new->be_v_offset - old->be_v_offset ==
 351                    new->be_f_offset - old->be_f_offset) &&
 352                   new->be_mdev == old->be_mdev));
 353 }
 354
 355 /* Adds new to appropriate list in bl, modifying new and removing existing
 356  * extents as appropriate to deal with overlaps.
 357  *
 358  * See bl_find_get_extent for list constraints.
 359  *
 360  * Refcount on new is already set.  If end up not using it, or error out,
 361  * need to put the reference.
 362  *
 363  * bl->bl_ext_lock is held by caller.
 364  */
 365 int
 366 bl_add_merge_extent(struct pnfs_block_layout *bl,
 367                      struct pnfs_block_extent *new)
 368 {
 369         struct pnfs_block_extent *be, *tmp;
 370         sector_t end = new->be_f_offset + new->be_length;
 371         struct list_head *list;
 372
 373         dprintk("%s enter with be=%p\n", __func__, new);
 374         print_bl_extent(new);
 375         list = &bl->bl_extents[bl_choose_list(new->be_state)];
 376         print_elist(list);
 377
 378         /* Scan for proper place to insert, extending new to the left
 379          * as much as possible.
 380          */
 381         list_for_each_entry_safe(be, tmp, list, be_node) {
 382                 if (new->be_f_offset < be->be_f_offset)
 383                         break;
 384                 if (end <= be->be_f_offset + be->be_length) {
 385                         /* new is a subset of existing be*/
 386                         if (extents_consistent(be, new)) {
 387                                 dprintk("%s: new is subset, ignoring\n",
 388                                         __func__);
 389                                 bl_put_extent(new);
 390                                 return 0;
 391                         } else
 392                                 goto out_err;
 393                 } else if (new->be_f_offset <=
 394                                 be->be_f_offset + be->be_length) {
 395                         /* new overlaps or abuts existing be */
 396                         if (extents_consistent(be, new)) {
 397                                 /* extend new to fully replace be */
 398                                 new->be_length += new->be_f_offset -
 399                                                   be->be_f_offset;
 400                                 new->be_f_offset = be->be_f_offset;
 401                                 new->be_v_offset = be->be_v_offset;
 402                                 dprintk("%s: removing %p\n", __func__, be);
 403                                 list_del(&be->be_node);
 404                                 bl_put_extent(be);
 405                         } else if (new->be_f_offset !=
 406                                    be->be_f_offset + be->be_length)
 407                                 goto out_err;
 408                 }
 409         }
 410         /* Note that if we never hit the above break, be will not point to a
 411          * valid extent.  However, in that case &be->be_node==list.
 412          */
 413         list_add_tail(&new->be_node, &be->be_node);
 414         dprintk("%s: inserting new\n", __func__);
 415         print_elist(list);
 416         /* Scan forward for overlaps.  If we find any, extend new and
 417          * remove the overlapped extent.
 418          */
 419         be = list_prepare_entry(new, list, be_node);
 420         list_for_each_entry_safe_continue(be, tmp, list, be_node) {
 421                 if (end < be->be_f_offset)
 422                         break;
 423                 /* new overlaps or abuts existing be */
 424                 if (extents_consistent(be, new)) {
 425                         if (end < be->be_f_offset + be->be_length) {
 426                                 /* extend new to fully cover be */
 427                                 end = be->be_f_offset + be->be_length;
 428                                 new->be_length = end - new->be_f_offset;
 429                         }
 430                         dprintk("%s: removing %p\n", __func__, be);
 431                         list_del(&be->be_node);
 432                         bl_put_extent(be);
 433                 } else if (end != be->be_f_offset) {
 434                         list_del(&new->be_node);
 435                         goto out_err;
 436                 }
 437         }
 438         dprintk("%s: after merging\n", __func__);
 439         print_elist(list);
 440         /* FIXME - The per-list consistency checks have all been done,
 441          * should now check cross-list consistency.
 442          */
 443         return 0;
 444
 445  out_err:
 446         bl_put_extent(new);
 447         return -EIO;
 448 }
 449
 450 /* Returns extent, or NULL.  If a second READ extent exists, it is returned
 451  * in cow_read, if given.
 452  *
 453  * The extents are kept in two seperate ordered lists, one for READ and NONE,
 454  * one for READWRITE and INVALID.  Within each list, we assume:
 455  * 1. Extents are ordered by file offset.
 456  * 2. For any given isect, there is at most one extents that matches.
 457  */
 458 struct pnfs_block_extent *
 459 bl_find_get_extent(struct pnfs_block_layout *bl, sector_t isect,
 460             struct pnfs_block_extent **cow_read)
 461 {
 462         struct pnfs_block_extent *be, *cow, *ret;
 463         int i;
 464
 465         dprintk("%s enter with isect %llu\n", __func__, (u64)isect);
 466         cow = ret = NULL;
 467         spin_lock(&bl->bl_ext_lock);
 468         for (i = 0; i < EXTENT_LISTS; i++) {
 469                 list_for_each_entry_reverse(be, &bl->bl_extents[i], be_node) {
 470                         if (isect >= be->be_f_offset + be->be_length)
 471                                 break;
 472                         if (isect >= be->be_f_offset) {
 473                                 /* We have found an extent */
 474                                 dprintk("%s Get %p (%i)\n", __func__, be,
 475                                         atomic_read(&be->be_refcnt.refcount));
 476                                 kref_get(&be->be_refcnt);
 477                                 if (!ret)
 478                                         ret = be;
 479                                 else if (be->be_state != PNFS_BLOCK_READ_DATA)
 480                                         bl_put_extent(be);
 481                                 else
 482                                         cow = be;
 483                                 break;
 484                         }
 485                 }
 486                 if (ret &&
 487                     (!cow_read || ret->be_state != PNFS_BLOCK_INVALID_DATA))
 488                         break;
 489         }
 490         spin_unlock(&bl->bl_ext_lock);
 491         if (cow_read)
 492                 *cow_read = cow;
 493         print_bl_extent(ret);
 494         return ret;
 495 }
 496
 497 /* Helper function to set_to_rw that initialize a new extent */
 498 static void
 499 _prep_new_extent(struct pnfs_block_extent *new,
 500                  struct pnfs_block_extent *orig,
 501                  sector_t offset, sector_t length, int state)
 502 {
 503         kref_init(&new->be_refcnt);
 504         /* don't need to INIT_LIST_HEAD(&new->be_node) */
 505         memcpy(&new->be_devid, &orig->be_devid, sizeof(struct nfs4_deviceid));
 506         new->be_mdev = orig->be_mdev;
 507         new->be_f_offset = offset;
 508         new->be_length = length;
 509         new->be_v_offset = orig->be_v_offset - orig->be_f_offset + offset;
 510         new->be_state = state;
 511         new->be_inval = orig->be_inval;
 512 }
 513
 514 /* Tries to merge be with extent in front of it in list.
 515  * Frees storage if not used.
 516  */
 517 static struct pnfs_block_extent *
 518 _front_merge(struct pnfs_block_extent *be, struct list_head *head,
 519              struct pnfs_block_extent *storage)
 520 {
 521         struct pnfs_block_extent *prev;
 522
 523         if (!storage)
 524                 goto no_merge;
 525         if (&be->be_node == head || be->be_node.prev == head)
 526                 goto no_merge;
 527         prev = list_entry(be->be_node.prev, struct pnfs_block_extent, be_node);
 528         if ((prev->be_f_offset + prev->be_length != be->be_f_offset) ||
 529             !extents_consistent(prev, be))
 530                 goto no_merge;
 531         _prep_new_extent(storage, prev, prev->be_f_offset,
 532                          prev->be_length + be->be_length, prev->be_state);
 533         list_replace(&prev->be_node, &storage->be_node);
 534         bl_put_extent(prev);
 535         list_del(&be->be_node);
 536         bl_put_extent(be);
 537         return storage;
 538
 539  no_merge:
 540         kfree(storage);
 541         return be;
 542 }