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 pnfs_inval_markings *marks,
 143                 u64 offset, u64 length)
 144 {
 145         u64 start, end, s;
 146         int count, i, used = 0, status = -ENOMEM;
 147         struct pnfs_inval_tracking **storage;
 148         struct my_tree  *tree = &marks->im_tree;
 149
 150         dprintk("%s(%llu, %llu) enter\n", __func__, offset, length);
 151         start = normalize(offset, tree->mtt_step_size);
 152         end = normalize_up(offset + length, tree->mtt_step_size);
 153         count = (int)(end - start) / (int)tree->mtt_step_size;
 154
 155         /* Pre-malloc what memory we might need */
 156         storage = kmalloc(sizeof(*storage) * count, GFP_NOFS);
 157         if (!storage)
 158                 return -ENOMEM;
 159         for (i = 0; i < count; i++) {
 160                 storage[i] = kmalloc(sizeof(struct pnfs_inval_tracking),
 161                                      GFP_NOFS);
 162                 if (!storage[i])
 163                         goto out_cleanup;
 164         }
 165
 166         spin_lock(&marks->im_lock);
 167         for (s = start; s < end; s += tree->mtt_step_size)
 168                 used += _add_entry(tree, s, INTERNAL_EXISTS, storage[used]);
 169         spin_unlock(&marks->im_lock);
 170
 171         status = 0;
 172
 173  out_cleanup:
 174         for (i = used; i < count; i++) {
 175                 if (!storage[i])
 176                         break;
 177                 kfree(storage[i]);
 178         }
 179         kfree(storage);
 180         return status;
 181 }
 182
 183 static void set_needs_init(sector_t *array, sector_t offset)
 184 {
 185         sector_t *p = array;
 186
 187         dprintk("%s enter\n", __func__);
 188         if (!p)
 189                 return;
 190         while (*p < offset)
 191                 p++;
 192         if (*p == offset)
 193                 return;
 194         else if (*p == ~0) {
 195                 *p++ = offset;
 196                 *p = ~0;
 197                 return;
 198         } else {
 199                 sector_t *save = p;
 200                 dprintk("%s Adding %llu\n", __func__, (u64)offset);
 201                 while (*p != ~0)
 202                         p++;
 203                 p++;
 204                 memmove(save + 1, save, (char *)p - (char *)save);
 205                 *save = offset;
 206                 return;
 207         }
 208 }
 209
 210 /* We are relying on page lock to serialize this */
 211 int bl_is_sector_init(struct pnfs_inval_markings *marks, sector_t isect)
 212 {
 213         int rv;
 214
 215         spin_lock(&marks->im_lock);
 216         rv = _has_tag(&marks->im_tree, isect, EXTENT_INITIALIZED);
 217         spin_unlock(&marks->im_lock);
 218         return rv;
 219 }
 220
 221 /* Assume start, end already sector aligned */
 222 static int
 223 _range_has_tag(struct my_tree *tree, u64 start, u64 end, int32_t tag)
 224 {
 225         struct pnfs_inval_tracking *pos;
 226         u64 expect = 0;
 227
 228         dprintk("%s(%llu, %llu, %i) enter\n", __func__, start, end, tag);
 229         list_for_each_entry_reverse(pos, &tree->mtt_stub, it_link) {
 230                 if (pos->it_sector >= end)
 231                         continue;
 232                 if (!expect) {
 233                         if ((pos->it_sector == end - tree->mtt_step_size) &&
 234                             (pos->it_tags & (1 << tag))) {
 235                                 expect = pos->it_sector - tree->mtt_step_size;
 236                                 if (pos->it_sector < tree->mtt_step_size || expect < start)
 237                                         return 1;
 238                                 continue;
 239                         } else {
 240                                 return 0;
 241                         }
 242                 }
 243                 if (pos->it_sector != expect || !(pos->it_tags & (1 << tag)))
 244                         return 0;
 245                 expect -= tree->mtt_step_size;
 246                 if (expect < start)
 247                         return 1;
 248         }
 249         return 0;
 250 }
 251
 252 static int is_range_written(struct pnfs_inval_markings *marks,
 253                             sector_t start, sector_t end)
 254 {
 255         int rv;
 256
 257         spin_lock(&marks->im_lock);
 258         rv = _range_has_tag(&marks->im_tree, start, end, EXTENT_WRITTEN);
 259         spin_unlock(&marks->im_lock);
 260         return rv;
 261 }
 262
 263 /* Marks sectors in [offest, offset_length) as having been initialized.
 264  * All lengths are step-aligned, where step is min(pagesize, blocksize).
 265  * Notes where partial block is initialized, and helps prepare it for
 266  * complete initialization later.
 267  */
 268 /* Currently assumes offset is page-aligned */
 269 int bl_mark_sectors_init(struct pnfs_inval_markings *marks,
 270                              sector_t offset, sector_t length,
 271                              sector_t **pages)
 272 {
 273         sector_t s, start, end;
 274         sector_t *array = NULL; /* Pages to mark */
 275
 276         dprintk("%s(offset=%llu,len=%llu) enter\n",
 277                 __func__, (u64)offset, (u64)length);
 278         s = max((sector_t) 3,
 279                 2 * (marks->im_block_size / (PAGE_CACHE_SECTORS)));
 280         dprintk("%s set max=%llu\n", __func__, (u64)s);
 281         if (pages) {
 282                 array = kmalloc(s * sizeof(sector_t), GFP_NOFS);
 283                 if (!array)
 284                         goto outerr;
 285                 array[0] = ~0;
 286         }
 287
 288         start = normalize(offset, marks->im_block_size);
 289         end = normalize_up(offset + length, marks->im_block_size);
 290         if (_preload_range(marks, start, end - start))
 291                 goto outerr;
 292
 293         spin_lock(&marks->im_lock);
 294
 295         for (s = normalize_up(start, PAGE_CACHE_SECTORS);
 296              s < offset; s += PAGE_CACHE_SECTORS) {
 297                 dprintk("%s pre-area pages\n", __func__);
 298                 /* Portion of used block is not initialized */
 299                 if (!_has_tag(&marks->im_tree, s, EXTENT_INITIALIZED))
 300                         set_needs_init(array, s);
 301         }
 302         if (_set_range(&marks->im_tree, EXTENT_INITIALIZED, offset, length))
 303                 goto out_unlock;
 304         for (s = normalize_up(offset + length, PAGE_CACHE_SECTORS);
 305              s < end; s += PAGE_CACHE_SECTORS) {
 306                 dprintk("%s post-area pages\n", __func__);
 307                 if (!_has_tag(&marks->im_tree, s, EXTENT_INITIALIZED))
 308                         set_needs_init(array, s);
 309         }
 310
 311         spin_unlock(&marks->im_lock);
 312
 313         if (pages) {
 314                 if (array[0] == ~0) {
 315                         kfree(array);
 316                         *pages = NULL;
 317                 } else
 318                         *pages = array;
 319         }
 320         return 0;
 321
 322  out_unlock:
 323         spin_unlock(&marks->im_lock);
 324  outerr:
 325         if (pages) {
 326                 kfree(array);
 327                 *pages = NULL;
 328         }
 329         return -ENOMEM;
 330 }
 331
 332 /* Marks sectors in [offest, offset+length) as having been written to disk.
 333  * All lengths should be block aligned.
 334  */
 335 static int mark_written_sectors(struct pnfs_inval_markings *marks,
 336                                 sector_t offset, sector_t length)
 337 {
 338         int status;
 339
 340         dprintk("%s(offset=%llu,len=%llu) enter\n", __func__,
 341                 (u64)offset, (u64)length);
 342         spin_lock(&marks->im_lock);
 343         status = _set_range(&marks->im_tree, EXTENT_WRITTEN, offset, length);
 344         spin_unlock(&marks->im_lock);
 345         return status;
 346 }
 347
 348 static void print_short_extent(struct pnfs_block_short_extent *be)
 349 {
 350         dprintk("PRINT SHORT EXTENT extent %p\n", be);
 351         if (be) {
 352                 dprintk("        be_f_offset %llu\n", (u64)be->bse_f_offset);
 353                 dprintk("        be_length   %llu\n", (u64)be->bse_length);
 354         }
 355 }
 356
 357 static void print_clist(struct list_head *list, unsigned int count)
 358 {
 359         struct pnfs_block_short_extent *be;
 360         unsigned int i = 0;
 361
 362         ifdebug(FACILITY) {
 363                 printk(KERN_DEBUG "****************\n");
 364                 printk(KERN_DEBUG "Extent list looks like:\n");
 365                 list_for_each_entry(be, list, bse_node) {
 366                         i++;
 367                         print_short_extent(be);
 368                 }
 369                 if (i != count)
 370                         printk(KERN_DEBUG "\n\nExpected %u entries\n\n\n", count);
 371                 printk(KERN_DEBUG "****************\n");
 372         }
 373 }
 374
 375 /* Note: In theory, we should do more checking that devid's match between
 376  * old and new, but if they don't, the lists are too corrupt to salvage anyway.
 377  */
 378 /* Note this is very similar to bl_add_merge_extent */
 379 static void add_to_commitlist(struct pnfs_block_layout *bl,
 380                               struct pnfs_block_short_extent *new)
 381 {
 382         struct list_head *clist = &bl->bl_commit;
 383         struct pnfs_block_short_extent *old, *save;
 384         sector_t end = new->bse_f_offset + new->bse_length;
 385
 386         dprintk("%s enter\n", __func__);
 387         print_short_extent(new);
 388         print_clist(clist, bl->bl_count);
 389         bl->bl_count++;
 390         /* Scan for proper place to insert, extending new to the left
 391          * as much as possible.
 392          */
 393         list_for_each_entry_safe(old, save, clist, bse_node) {
 394                 if (new->bse_f_offset < old->bse_f_offset)
 395                         break;
 396                 if (end <= old->bse_f_offset + old->bse_length) {
 397                         /* Range is already in list */
 398                         bl->bl_count--;
 399                         kfree(new);
 400                         return;
 401                 } else if (new->bse_f_offset <=
 402                                 old->bse_f_offset + old->bse_length) {
 403                         /* new overlaps or abuts existing be */
 404                         if (new->bse_mdev == old->bse_mdev) {
 405                                 /* extend new to fully replace old */
 406                                 new->bse_length += new->bse_f_offset -
 407                                                 old->bse_f_offset;
 408                                 new->bse_f_offset = old->bse_f_offset;
 409                                 list_del(&old->bse_node);
 410                                 bl->bl_count--;
 411                                 kfree(old);
 412                         }
 413                 }
 414         }
 415         /* Note that if we never hit the above break, old will not point to a
 416          * valid extent.  However, in that case &old->bse_node==list.
 417          */
 418         list_add_tail(&new->bse_node, &old->bse_node);
 419         /* Scan forward for overlaps.  If we find any, extend new and
 420          * remove the overlapped extent.
 421          */
 422         old = list_prepare_entry(new, clist, bse_node);
 423         list_for_each_entry_safe_continue(old, save, clist, bse_node) {
 424                 if (end < old->bse_f_offset)
 425                         break;
 426                 /* new overlaps or abuts old */
 427                 if (new->bse_mdev == old->bse_mdev) {
 428                         if (end < old->bse_f_offset + old->bse_length) {
 429                                 /* extend new to fully cover old */
 430                                 end = old->bse_f_offset + old->bse_length;
 431                                 new->bse_length = end - new->bse_f_offset;
 432                         }
 433                         list_del(&old->bse_node);
 434                         bl->bl_count--;
 435                         kfree(old);
 436                 }
 437         }
 438         dprintk("%s: after merging\n", __func__);
 439         print_clist(clist, bl->bl_count);
 440 }
 441
 442 /* Note the range described by offset, length is guaranteed to be contained
 443  * within be.
 444  */
 445 int bl_mark_for_commit(struct pnfs_block_extent *be,
 446                     sector_t offset, sector_t length)
 447 {
 448         sector_t new_end, end = offset + length;
 449         struct pnfs_block_short_extent *new;
 450         struct pnfs_block_layout *bl = container_of(be->be_inval,
 451                                                     struct pnfs_block_layout,
 452                                                     bl_inval);
 453
 454         new = kmalloc(sizeof(*new), GFP_NOFS);
 455         if (!new)
 456                 return -ENOMEM;
 457
 458         mark_written_sectors(be->be_inval, offset, length);
 459         /* We want to add the range to commit list, but it must be
 460          * block-normalized, and verified that the normalized range has
 461          * been entirely written to disk.
 462          */
 463         new->bse_f_offset = offset;
 464         offset = normalize(offset, bl->bl_blocksize);
 465         if (offset < new->bse_f_offset) {
 466                 if (is_range_written(be->be_inval, offset, new->bse_f_offset))
 467                         new->bse_f_offset = offset;
 468                 else
 469                         new->bse_f_offset = offset + bl->bl_blocksize;
 470         }
 471         new_end = normalize_up(end, bl->bl_blocksize);
 472         if (end < new_end) {
 473                 if (is_range_written(be->be_inval, end, new_end))
 474                         end = new_end;
 475                 else
 476                         end = new_end - bl->bl_blocksize;
 477         }
 478         if (end <= new->bse_f_offset) {
 479                 kfree(new);
 480                 return 0;
 481         }
 482         new->bse_length = end - new->bse_f_offset;
 483         new->bse_devid = be->be_devid;
 484         new->bse_mdev = be->be_mdev;
 485
 486         spin_lock(&bl->bl_ext_lock);
 487         /* new will be freed, either by add_to_commitlist if it decides not
 488          * to use it, or after LAYOUTCOMMIT uses it in the commitlist.
 489          */
 490         add_to_commitlist(bl, new);
 491         spin_unlock(&bl->bl_ext_lock);
 492         return 0;
 493 }
 494
 495 static void print_bl_extent(struct pnfs_block_extent *be)
 496 {
 497         dprintk("PRINT EXTENT extent %p\n", be);
 498         if (be) {
 499                 dprintk("        be_f_offset %llu\n", (u64)be->be_f_offset);
 500                 dprintk("        be_length   %llu\n", (u64)be->be_length);
 501                 dprintk("        be_v_offset %llu\n", (u64)be->be_v_offset);
 502                 dprintk("        be_state    %d\n", be->be_state);
 503         }
 504 }
 505
 506 static void
 507 destroy_extent(struct kref *kref)
 508 {
 509         struct pnfs_block_extent *be;
 510
 511         be = container_of(kref, struct pnfs_block_extent, be_refcnt);
 512         dprintk("%s be=%p\n", __func__, be);
 513         kfree(be);
 514 }
 515
 516 void
 517 bl_put_extent(struct pnfs_block_extent *be)
 518 {
 519         if (be) {
 520                 dprintk("%s enter %p (%i)\n", __func__, be,
 521                         atomic_read(&be->be_refcnt.refcount));
 522                 kref_put(&be->be_refcnt, destroy_extent);
 523         }
 524 }
 525
 526 struct pnfs_block_extent *bl_alloc_extent(void)
 527 {
 528         struct pnfs_block_extent *be;
 529
 530         be = kmalloc(sizeof(struct pnfs_block_extent), GFP_NOFS);
 531         if (!be)
 532                 return NULL;
 533         INIT_LIST_HEAD(&be->be_node);
 534         kref_init(&be->be_refcnt);
 535         be->be_inval = NULL;
 536         return be;
 537 }
 538
 539 static void print_elist(struct list_head *list)
 540 {
 541         struct pnfs_block_extent *be;
 542         dprintk("****************\n");
 543         dprintk("Extent list looks like:\n");
 544         list_for_each_entry(be, list, be_node) {
 545                 print_bl_extent(be);
 546         }
 547         dprintk("****************\n");
 548 }
 549
 550 static inline int
 551 extents_consistent(struct pnfs_block_extent *old, struct pnfs_block_extent *new)
 552 {
 553         /* Note this assumes new->be_f_offset >= old->be_f_offset */
 554         return (new->be_state == old->be_state) &&
 555                 ((new->be_state == PNFS_BLOCK_NONE_DATA) ||
 556                  ((new->be_v_offset - old->be_v_offset ==
 557                    new->be_f_offset - old->be_f_offset) &&
 558                   new->be_mdev == old->be_mdev));
 559 }
 560
 561 /* Adds new to appropriate list in bl, modifying new and removing existing
 562  * extents as appropriate to deal with overlaps.
 563  *
 564  * See bl_find_get_extent for list constraints.
 565  *
 566  * Refcount on new is already set.  If end up not using it, or error out,
 567  * need to put the reference.
 568  *
 569  * bl->bl_ext_lock is held by caller.
 570  */
 571 int
 572 bl_add_merge_extent(struct pnfs_block_layout *bl,
 573                      struct pnfs_block_extent *new)
 574 {
 575         struct pnfs_block_extent *be, *tmp;
 576         sector_t end = new->be_f_offset + new->be_length;
 577         struct list_head *list;
 578
 579         dprintk("%s enter with be=%p\n", __func__, new);
 580         print_bl_extent(new);
 581         list = &bl->bl_extents[bl_choose_list(new->be_state)];
 582         print_elist(list);
 583
 584         /* Scan for proper place to insert, extending new to the left
 585          * as much as possible.
 586          */
 587         list_for_each_entry_safe_reverse(be, tmp, list, be_node) {
 588                 if (new->be_f_offset >= be->be_f_offset + be->be_length)
 589                         break;
 590                 if (new->be_f_offset >= be->be_f_offset) {
 591                         if (end <= be->be_f_offset + be->be_length) {
 592                                 /* new is a subset of existing be*/
 593                                 if (extents_consistent(be, new)) {
 594                                         dprintk("%s: new is subset, ignoring\n",
 595                                                 __func__);
 596                                         bl_put_extent(new);
 597                                         return 0;
 598                                 } else {
 599                                         goto out_err;
 600                                 }
 601                         } else {
 602                                 /* |<--   be   -->|
 603                                  *          |<--   new   -->| */
 604                                 if (extents_consistent(be, new)) {
 605                                         /* extend new to fully replace be */
 606                                         new->be_length += new->be_f_offset -
 607                                                 be->be_f_offset;
 608                                         new->be_f_offset = be->be_f_offset;
 609                                         new->be_v_offset = be->be_v_offset;
 610                                         dprintk("%s: removing %p\n", __func__, be);
 611                                         list_del(&be->be_node);
 612                                         bl_put_extent(be);
 613                                 } else {
 614                                         goto out_err;
 615                                 }
 616                         }
 617                 } else if (end >= be->be_f_offset + be->be_length) {
 618                         /* new extent overlap existing be */
 619                         if (extents_consistent(be, new)) {
 620                                 /* extend new to fully replace be */
 621                                 dprintk("%s: removing %p\n", __func__, be);
 622                                 list_del(&be->be_node);
 623                                 bl_put_extent(be);
 624                         } else {
 625                                 goto out_err;
 626                         }
 627                 } else if (end > be->be_f_offset) {
 628                         /*           |<--   be   -->|
 629                          *|<--   new   -->| */
 630                         if (extents_consistent(new, be)) {
 631                                 /* extend new to fully replace be */
 632                                 new->be_length += be->be_f_offset + be->be_length -
 633                                         new->be_f_offset - new->be_length;
 634                                 dprintk("%s: removing %p\n", __func__, be);
 635                                 list_del(&be->be_node);
 636                                 bl_put_extent(be);
 637                         } else {
 638                                 goto out_err;
 639                         }
 640                 }
 641         }
 642         /* Note that if we never hit the above break, be will not point to a
 643          * valid extent.  However, in that case &be->be_node==list.
 644          */
 645         list_add(&new->be_node, &be->be_node);
 646         dprintk("%s: inserting new\n", __func__);
 647         print_elist(list);
 648         /* FIXME - The per-list consistency checks have all been done,
 649          * should now check cross-list consistency.
 650          */
 651         return 0;
 652
 653  out_err:
 654         bl_put_extent(new);
 655         return -EIO;
 656 }
 657
 658 /* Returns extent, or NULL.  If a second READ extent exists, it is returned
 659  * in cow_read, if given.
 660  *
 661  * The extents are kept in two seperate ordered lists, one for READ and NONE,
 662  * one for READWRITE and INVALID.  Within each list, we assume:
 663  * 1. Extents are ordered by file offset.
 664  * 2. For any given isect, there is at most one extents that matches.
 665  */
 666 struct pnfs_block_extent *
 667 bl_find_get_extent(struct pnfs_block_layout *bl, sector_t isect,
 668             struct pnfs_block_extent **cow_read)
 669 {
 670         struct pnfs_block_extent *be, *cow, *ret;
 671         int i;
 672
 673         dprintk("%s enter with isect %llu\n", __func__, (u64)isect);
 674         cow = ret = NULL;
 675         spin_lock(&bl->bl_ext_lock);
 676         for (i = 0; i < EXTENT_LISTS; i++) {
 677                 list_for_each_entry_reverse(be, &bl->bl_extents[i], be_node) {
 678                         if (isect >= be->be_f_offset + be->be_length)
 679                                 break;
 680                         if (isect >= be->be_f_offset) {
 681                                 /* We have found an extent */
 682                                 dprintk("%s Get %p (%i)\n", __func__, be,
 683                                         atomic_read(&be->be_refcnt.refcount));
 684                                 kref_get(&be->be_refcnt);
 685                                 if (!ret)
 686                                         ret = be;
 687                                 else if (be->be_state != PNFS_BLOCK_READ_DATA)
 688                                         bl_put_extent(be);
 689                                 else
 690                                         cow = be;
 691                                 break;
 692                         }
 693                 }
 694                 if (ret &&
 695                     (!cow_read || ret->be_state != PNFS_BLOCK_INVALID_DATA))
 696                         break;
 697         }
 698         spin_unlock(&bl->bl_ext_lock);
 699         if (cow_read)
 700                 *cow_read = cow;
 701         print_bl_extent(ret);
 702         return ret;
 703 }
 704
 705 /* Similar to bl_find_get_extent, but called with lock held, and ignores cow */
 706 static struct pnfs_block_extent *
 707 bl_find_get_extent_locked(struct pnfs_block_layout *bl, sector_t isect)
 708 {
 709         struct pnfs_block_extent *be, *ret = NULL;
 710         int i;
 711
 712         dprintk("%s enter with isect %llu\n", __func__, (u64)isect);
 713         for (i = 0; i < EXTENT_LISTS; i++) {
 714                 if (ret)
 715                         break;
 716                 list_for_each_entry_reverse(be, &bl->bl_extents[i], be_node) {
 717                         if (isect >= be->be_f_offset + be->be_length)
 718                                 break;
 719                         if (isect >= be->be_f_offset) {
 720                                 /* We have found an extent */
 721                                 dprintk("%s Get %p (%i)\n", __func__, be,
 722                                         atomic_read(&be->be_refcnt.refcount));
 723                                 kref_get(&be->be_refcnt);
 724                                 ret = be;
 725                                 break;
 726                         }
 727                 }
 728         }
 729         print_bl_extent(ret);
 730         return ret;
 731 }
 732
 733 int
 734 encode_pnfs_block_layoutupdate(struct pnfs_block_layout *bl,
 735                                struct xdr_stream *xdr,
 736                                const struct nfs4_layoutcommit_args *arg)
 737 {
 738         struct pnfs_block_short_extent *lce, *save;
 739         unsigned int count = 0;
 740         __be32 *p, *xdr_start;
 741
 742         dprintk("%s enter\n", __func__);
 743         /* BUG - creation of bl_commit is buggy - need to wait for
 744          * entire block to be marked WRITTEN before it can be added.
 745          */
 746         spin_lock(&bl->bl_ext_lock);
 747         /* Want to adjust for possible truncate */
 748         /* We now want to adjust argument range */
 749
 750         /* XDR encode the ranges found */
 751         xdr_start = xdr_reserve_space(xdr, 8);
 752         if (!xdr_start)
 753                 goto out;
 754         list_for_each_entry_safe(lce, save, &bl->bl_commit, bse_node) {
 755                 p = xdr_reserve_space(xdr, 7 * 4 + sizeof(lce->bse_devid.data));
 756                 if (!p)
 757                         break;
 758                 p = xdr_encode_opaque_fixed(p, lce->bse_devid.data, NFS4_DEVICEID4_SIZE);
 759                 p = xdr_encode_hyper(p, lce->bse_f_offset << SECTOR_SHIFT);
 760                 p = xdr_encode_hyper(p, lce->bse_length << SECTOR_SHIFT);
 761                 p = xdr_encode_hyper(p, 0LL);
 762                 *p++ = cpu_to_be32(PNFS_BLOCK_READWRITE_DATA);
 763                 list_del(&lce->bse_node);
 764                 list_add_tail(&lce->bse_node, &bl->bl_committing);
 765                 bl->bl_count--;
 766                 count++;
 767         }
 768         xdr_start[0] = cpu_to_be32((xdr->p - xdr_start - 1) * 4);
 769         xdr_start[1] = cpu_to_be32(count);
 770 out:
 771         spin_unlock(&bl->bl_ext_lock);
 772         dprintk("%s found %i ranges\n", __func__, count);
 773         return 0;
 774 }
 775
 776 /* Helper function to set_to_rw that initialize a new extent */
 777 static void
 778 _prep_new_extent(struct pnfs_block_extent *new,
 779                  struct pnfs_block_extent *orig,
 780                  sector_t offset, sector_t length, int state)
 781 {
 782         kref_init(&new->be_refcnt);
 783         /* don't need to INIT_LIST_HEAD(&new->be_node) */
 784         memcpy(&new->be_devid, &orig->be_devid, sizeof(struct nfs4_deviceid));
 785         new->be_mdev = orig->be_mdev;
 786         new->be_f_offset = offset;
 787         new->be_length = length;
 788         new->be_v_offset = orig->be_v_offset - orig->be_f_offset + offset;
 789         new->be_state = state;
 790         new->be_inval = orig->be_inval;
 791 }
 792
 793 /* Tries to merge be with extent in front of it in list.
 794  * Frees storage if not used.
 795  */
 796 static struct pnfs_block_extent *
 797 _front_merge(struct pnfs_block_extent *be, struct list_head *head,
 798              struct pnfs_block_extent *storage)
 799 {
 800         struct pnfs_block_extent *prev;
 801
 802         if (!storage)
 803                 goto no_merge;
 804         if (&be->be_node == head || be->be_node.prev == head)
 805                 goto no_merge;
 806         prev = list_entry(be->be_node.prev, struct pnfs_block_extent, be_node);
 807         if ((prev->be_f_offset + prev->be_length != be->be_f_offset) ||
 808             !extents_consistent(prev, be))
 809                 goto no_merge;
 810         _prep_new_extent(storage, prev, prev->be_f_offset,
 811                          prev->be_length + be->be_length, prev->be_state);
 812         list_replace(&prev->be_node, &storage->be_node);
 813         bl_put_extent(prev);
 814         list_del(&be->be_node);
 815         bl_put_extent(be);
 816         return storage;
 817
 818  no_merge:
 819         kfree(storage);
 820         return be;
 821 }
 822
 823 static u64
 824 set_to_rw(struct pnfs_block_layout *bl, u64 offset, u64 length)
 825 {
 826         u64 rv = offset + length;
 827         struct pnfs_block_extent *be, *e1, *e2, *e3, *new, *old;
 828         struct pnfs_block_extent *children[3];
 829         struct pnfs_block_extent *merge1 = NULL, *merge2 = NULL;
 830         int i = 0, j;
 831
 832         dprintk("%s(%llu, %llu)\n", __func__, offset, length);
 833         /* Create storage for up to three new extents e1, e2, e3 */
 834         e1 = kmalloc(sizeof(*e1), GFP_ATOMIC);
 835         e2 = kmalloc(sizeof(*e2), GFP_ATOMIC);
 836         e3 = kmalloc(sizeof(*e3), GFP_ATOMIC);
 837         /* BUG - we are ignoring any failure */
 838         if (!e1 || !e2 || !e3)
 839                 goto out_nosplit;
 840
 841         spin_lock(&bl->bl_ext_lock);
 842         be = bl_find_get_extent_locked(bl, offset);
 843         rv = be->be_f_offset + be->be_length;
 844         if (be->be_state != PNFS_BLOCK_INVALID_DATA) {
 845                 spin_unlock(&bl->bl_ext_lock);
 846                 goto out_nosplit;
 847         }
 848         /* Add e* to children, bumping e*'s krefs */
 849         if (be->be_f_offset != offset) {
 850                 _prep_new_extent(e1, be, be->be_f_offset,
 851                                  offset - be->be_f_offset,
 852                                  PNFS_BLOCK_INVALID_DATA);
 853                 children[i++] = e1;
 854                 print_bl_extent(e1);
 855         } else
 856                 merge1 = e1;
 857         _prep_new_extent(e2, be, offset,
 858                          min(length, be->be_f_offset + be->be_length - offset),
 859                          PNFS_BLOCK_READWRITE_DATA);
 860         children[i++] = e2;
 861         print_bl_extent(e2);
 862         if (offset + length < be->be_f_offset + be->be_length) {
 863                 _prep_new_extent(e3, be, e2->be_f_offset + e2->be_length,
 864                                  be->be_f_offset + be->be_length -
 865                                  offset - length,
 866                                  PNFS_BLOCK_INVALID_DATA);
 867                 children[i++] = e3;
 868                 print_bl_extent(e3);
 869         } else
 870                 merge2 = e3;
 871
 872         /* Remove be from list, and insert the e* */
 873         /* We don't get refs on e*, since this list is the base reference
 874          * set when init'ed.
 875          */
 876         if (i < 3)
 877                 children[i] = NULL;
 878         new = children[0];
 879         list_replace(&be->be_node, &new->be_node);
 880         bl_put_extent(be);
 881         new = _front_merge(new, &bl->bl_extents[RW_EXTENT], merge1);
 882         for (j = 1; j < i; j++) {
 883                 old = new;
 884                 new = children[j];
 885                 list_add(&new->be_node, &old->be_node);
 886         }
 887         if (merge2) {
 888                 /* This is a HACK, should just create a _back_merge function */
 889                 new = list_entry(new->be_node.next,
 890                                  struct pnfs_block_extent, be_node);
 891                 new = _front_merge(new, &bl->bl_extents[RW_EXTENT], merge2);
 892         }
 893         spin_unlock(&bl->bl_ext_lock);
 894
 895         /* Since we removed the base reference above, be is now scheduled for
 896          * destruction.
 897          */
 898         bl_put_extent(be);
 899         dprintk("%s returns %llu after split\n", __func__, rv);
 900         return rv;
 901
 902  out_nosplit:
 903         kfree(e1);
 904         kfree(e2);
 905         kfree(e3);
 906         dprintk("%s returns %llu without splitting\n", __func__, rv);
 907         return rv;
 908 }
 909
 910 void
 911 clean_pnfs_block_layoutupdate(struct pnfs_block_layout *bl,
 912                               const struct nfs4_layoutcommit_args *arg,
 913                               int status)
 914 {
 915         struct pnfs_block_short_extent *lce, *save;
 916
 917         dprintk("%s status %d\n", __func__, status);
 918         list_for_each_entry_safe(lce, save, &bl->bl_committing, bse_node) {
 919                 if (likely(!status)) {
 920                         u64 offset = lce->bse_f_offset;
 921                         u64 end = offset + lce->bse_length;
 922
 923                         do {
 924                                 offset = set_to_rw(bl, offset, end - offset);
 925                         } while (offset < end);
 926                         list_del(&lce->bse_node);
 927
 928                         kfree(lce);
 929                 } else {
 930                         list_del(&lce->bse_node);
 931                         spin_lock(&bl->bl_ext_lock);
 932                         add_to_commitlist(bl, lce);
 933                         spin_unlock(&bl->bl_ext_lock);
 934                 }
 935         }
 936 }