blob: 84bf24087720f68cf879d98cb343fd1dc33ac203 [file] [log] [blame]
Fred Isaman9e692962011-07-30 20:52:41 -04001/*
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
Fred Isamanc1c2a4c2011-07-30 20:52:49 -040036/* 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 */
44static 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
50static 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 */
58static 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
74static inline
75int _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 */
92static 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 */
129static 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 */
142static 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
182static 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 */
210int 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 */
226int 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
Fred Isaman90ace122011-07-30 20:52:51 -0400289/* Marks sectors in [offest, offset+length) as having been written to disk.
290 * All lengths should be block aligned.
291 */
292static int mark_written_sectors(struct pnfs_inval_markings *marks,
293 sector_t offset, sector_t length)
294{
295 int status;
296
297 dprintk("%s(offset=%llu,len=%llu) enter\n", __func__,
298 (u64)offset, (u64)length);
299 spin_lock(&marks->im_lock);
300 status = _set_range(&marks->im_tree, EXTENT_WRITTEN, offset, length);
301 spin_unlock(&marks->im_lock);
302 return status;
303}
304
305static void print_short_extent(struct pnfs_block_short_extent *be)
306{
307 dprintk("PRINT SHORT EXTENT extent %p\n", be);
308 if (be) {
309 dprintk(" be_f_offset %llu\n", (u64)be->bse_f_offset);
310 dprintk(" be_length %llu\n", (u64)be->bse_length);
311 }
312}
313
314static void print_clist(struct list_head *list, unsigned int count)
315{
316 struct pnfs_block_short_extent *be;
317 unsigned int i = 0;
318
319 ifdebug(FACILITY) {
320 printk(KERN_DEBUG "****************\n");
321 printk(KERN_DEBUG "Extent list looks like:\n");
322 list_for_each_entry(be, list, bse_node) {
323 i++;
324 print_short_extent(be);
325 }
326 if (i != count)
327 printk(KERN_DEBUG "\n\nExpected %u entries\n\n\n", count);
328 printk(KERN_DEBUG "****************\n");
329 }
330}
331
Fred Isaman9e692962011-07-30 20:52:41 -0400332static void print_bl_extent(struct pnfs_block_extent *be)
333{
334 dprintk("PRINT EXTENT extent %p\n", be);
335 if (be) {
336 dprintk(" be_f_offset %llu\n", (u64)be->be_f_offset);
337 dprintk(" be_length %llu\n", (u64)be->be_length);
338 dprintk(" be_v_offset %llu\n", (u64)be->be_v_offset);
339 dprintk(" be_state %d\n", be->be_state);
340 }
341}
342
343static void
344destroy_extent(struct kref *kref)
345{
346 struct pnfs_block_extent *be;
347
348 be = container_of(kref, struct pnfs_block_extent, be_refcnt);
349 dprintk("%s be=%p\n", __func__, be);
350 kfree(be);
351}
352
353void
354bl_put_extent(struct pnfs_block_extent *be)
355{
356 if (be) {
357 dprintk("%s enter %p (%i)\n", __func__, be,
358 atomic_read(&be->be_refcnt.refcount));
359 kref_put(&be->be_refcnt, destroy_extent);
360 }
361}
362
363struct pnfs_block_extent *bl_alloc_extent(void)
364{
365 struct pnfs_block_extent *be;
366
367 be = kmalloc(sizeof(struct pnfs_block_extent), GFP_NOFS);
368 if (!be)
369 return NULL;
370 INIT_LIST_HEAD(&be->be_node);
371 kref_init(&be->be_refcnt);
372 be->be_inval = NULL;
373 return be;
374}
375
376static void print_elist(struct list_head *list)
377{
378 struct pnfs_block_extent *be;
379 dprintk("****************\n");
380 dprintk("Extent list looks like:\n");
381 list_for_each_entry(be, list, be_node) {
382 print_bl_extent(be);
383 }
384 dprintk("****************\n");
385}
Fred Isaman03341d22011-07-30 20:52:45 -0400386
387static inline int
388extents_consistent(struct pnfs_block_extent *old, struct pnfs_block_extent *new)
389{
390 /* Note this assumes new->be_f_offset >= old->be_f_offset */
391 return (new->be_state == old->be_state) &&
392 ((new->be_state == PNFS_BLOCK_NONE_DATA) ||
393 ((new->be_v_offset - old->be_v_offset ==
394 new->be_f_offset - old->be_f_offset) &&
395 new->be_mdev == old->be_mdev));
396}
397
398/* Adds new to appropriate list in bl, modifying new and removing existing
399 * extents as appropriate to deal with overlaps.
400 *
401 * See bl_find_get_extent for list constraints.
402 *
403 * Refcount on new is already set. If end up not using it, or error out,
404 * need to put the reference.
405 *
406 * bl->bl_ext_lock is held by caller.
407 */
408int
409bl_add_merge_extent(struct pnfs_block_layout *bl,
410 struct pnfs_block_extent *new)
411{
412 struct pnfs_block_extent *be, *tmp;
413 sector_t end = new->be_f_offset + new->be_length;
414 struct list_head *list;
415
416 dprintk("%s enter with be=%p\n", __func__, new);
417 print_bl_extent(new);
418 list = &bl->bl_extents[bl_choose_list(new->be_state)];
419 print_elist(list);
420
421 /* Scan for proper place to insert, extending new to the left
422 * as much as possible.
423 */
Fred Isaman90ace122011-07-30 20:52:51 -0400424 list_for_each_entry_safe_reverse(be, tmp, list, be_node) {
425 if (new->be_f_offset >= be->be_f_offset + be->be_length)
Fred Isaman03341d22011-07-30 20:52:45 -0400426 break;
Fred Isaman90ace122011-07-30 20:52:51 -0400427 if (new->be_f_offset >= be->be_f_offset) {
428 if (end <= be->be_f_offset + be->be_length) {
429 /* new is a subset of existing be*/
430 if (extents_consistent(be, new)) {
431 dprintk("%s: new is subset, ignoring\n",
432 __func__);
433 bl_put_extent(new);
434 return 0;
435 } else {
436 goto out_err;
437 }
438 } else {
439 /* |<-- be -->|
440 * |<-- new -->| */
441 if (extents_consistent(be, new)) {
442 /* extend new to fully replace be */
443 new->be_length += new->be_f_offset -
444 be->be_f_offset;
445 new->be_f_offset = be->be_f_offset;
446 new->be_v_offset = be->be_v_offset;
447 dprintk("%s: removing %p\n", __func__, be);
448 list_del(&be->be_node);
449 bl_put_extent(be);
450 } else {
451 goto out_err;
452 }
453 }
454 } else if (end >= be->be_f_offset + be->be_length) {
455 /* new extent overlap existing be */
Fred Isaman03341d22011-07-30 20:52:45 -0400456 if (extents_consistent(be, new)) {
457 /* extend new to fully replace be */
Fred Isaman03341d22011-07-30 20:52:45 -0400458 dprintk("%s: removing %p\n", __func__, be);
459 list_del(&be->be_node);
460 bl_put_extent(be);
Fred Isaman90ace122011-07-30 20:52:51 -0400461 } else {
Fred Isaman03341d22011-07-30 20:52:45 -0400462 goto out_err;
Fred Isaman90ace122011-07-30 20:52:51 -0400463 }
464 } else if (end > be->be_f_offset) {
465 /* |<-- be -->|
466 *|<-- new -->| */
467 if (extents_consistent(new, be)) {
468 /* extend new to fully replace be */
469 new->be_length += be->be_f_offset + be->be_length -
470 new->be_f_offset - new->be_length;
471 dprintk("%s: removing %p\n", __func__, be);
472 list_del(&be->be_node);
473 bl_put_extent(be);
474 } else {
475 goto out_err;
476 }
Fred Isaman03341d22011-07-30 20:52:45 -0400477 }
478 }
479 /* Note that if we never hit the above break, be will not point to a
480 * valid extent. However, in that case &be->be_node==list.
481 */
Fred Isaman90ace122011-07-30 20:52:51 -0400482 list_add(&new->be_node, &be->be_node);
Fred Isaman03341d22011-07-30 20:52:45 -0400483 dprintk("%s: inserting new\n", __func__);
484 print_elist(list);
Fred Isaman03341d22011-07-30 20:52:45 -0400485 /* FIXME - The per-list consistency checks have all been done,
486 * should now check cross-list consistency.
487 */
488 return 0;
489
490 out_err:
491 bl_put_extent(new);
492 return -EIO;
493}
Fred Isaman6d742ba2011-07-30 20:52:48 -0400494
495/* Returns extent, or NULL. If a second READ extent exists, it is returned
496 * in cow_read, if given.
497 *
498 * The extents are kept in two seperate ordered lists, one for READ and NONE,
499 * one for READWRITE and INVALID. Within each list, we assume:
500 * 1. Extents are ordered by file offset.
501 * 2. For any given isect, there is at most one extents that matches.
502 */
503struct pnfs_block_extent *
504bl_find_get_extent(struct pnfs_block_layout *bl, sector_t isect,
505 struct pnfs_block_extent **cow_read)
506{
507 struct pnfs_block_extent *be, *cow, *ret;
508 int i;
509
510 dprintk("%s enter with isect %llu\n", __func__, (u64)isect);
511 cow = ret = NULL;
512 spin_lock(&bl->bl_ext_lock);
513 for (i = 0; i < EXTENT_LISTS; i++) {
514 list_for_each_entry_reverse(be, &bl->bl_extents[i], be_node) {
515 if (isect >= be->be_f_offset + be->be_length)
516 break;
517 if (isect >= be->be_f_offset) {
518 /* We have found an extent */
519 dprintk("%s Get %p (%i)\n", __func__, be,
520 atomic_read(&be->be_refcnt.refcount));
521 kref_get(&be->be_refcnt);
522 if (!ret)
523 ret = be;
524 else if (be->be_state != PNFS_BLOCK_READ_DATA)
525 bl_put_extent(be);
526 else
527 cow = be;
528 break;
529 }
530 }
531 if (ret &&
532 (!cow_read || ret->be_state != PNFS_BLOCK_INVALID_DATA))
533 break;
534 }
535 spin_unlock(&bl->bl_ext_lock);
536 if (cow_read)
537 *cow_read = cow;
538 print_bl_extent(ret);
539 return ret;
540}
Fred Isaman9f377042011-07-30 20:52:50 -0400541
Fred Isaman90ace122011-07-30 20:52:51 -0400542int
543encode_pnfs_block_layoutupdate(struct pnfs_block_layout *bl,
544 struct xdr_stream *xdr,
545 const struct nfs4_layoutcommit_args *arg)
546{
547 struct pnfs_block_short_extent *lce, *save;
548 unsigned int count = 0;
549 __be32 *p, *xdr_start;
550
551 dprintk("%s enter\n", __func__);
552 /* BUG - creation of bl_commit is buggy - need to wait for
553 * entire block to be marked WRITTEN before it can be added.
554 */
555 spin_lock(&bl->bl_ext_lock);
556 /* Want to adjust for possible truncate */
557 /* We now want to adjust argument range */
558
559 /* XDR encode the ranges found */
560 xdr_start = xdr_reserve_space(xdr, 8);
561 if (!xdr_start)
562 goto out;
563 list_for_each_entry_safe(lce, save, &bl->bl_commit, bse_node) {
564 p = xdr_reserve_space(xdr, 7 * 4 + sizeof(lce->bse_devid.data));
565 if (!p)
566 break;
567 p = xdr_encode_opaque_fixed(p, lce->bse_devid.data, NFS4_DEVICEID4_SIZE);
568 p = xdr_encode_hyper(p, lce->bse_f_offset << SECTOR_SHIFT);
569 p = xdr_encode_hyper(p, lce->bse_length << SECTOR_SHIFT);
570 p = xdr_encode_hyper(p, 0LL);
571 *p++ = cpu_to_be32(PNFS_BLOCK_READWRITE_DATA);
572 list_del(&lce->bse_node);
573 list_add_tail(&lce->bse_node, &bl->bl_committing);
574 bl->bl_count--;
575 count++;
576 }
577 xdr_start[0] = cpu_to_be32((xdr->p - xdr_start - 1) * 4);
578 xdr_start[1] = cpu_to_be32(count);
579out:
580 spin_unlock(&bl->bl_ext_lock);
581 dprintk("%s found %i ranges\n", __func__, count);
582 return 0;
583}
584
Fred Isaman9f377042011-07-30 20:52:50 -0400585/* Helper function to set_to_rw that initialize a new extent */
586static void
587_prep_new_extent(struct pnfs_block_extent *new,
588 struct pnfs_block_extent *orig,
589 sector_t offset, sector_t length, int state)
590{
591 kref_init(&new->be_refcnt);
592 /* don't need to INIT_LIST_HEAD(&new->be_node) */
593 memcpy(&new->be_devid, &orig->be_devid, sizeof(struct nfs4_deviceid));
594 new->be_mdev = orig->be_mdev;
595 new->be_f_offset = offset;
596 new->be_length = length;
597 new->be_v_offset = orig->be_v_offset - orig->be_f_offset + offset;
598 new->be_state = state;
599 new->be_inval = orig->be_inval;
600}
601
602/* Tries to merge be with extent in front of it in list.
603 * Frees storage if not used.
604 */
605static struct pnfs_block_extent *
606_front_merge(struct pnfs_block_extent *be, struct list_head *head,
607 struct pnfs_block_extent *storage)
608{
609 struct pnfs_block_extent *prev;
610
611 if (!storage)
612 goto no_merge;
613 if (&be->be_node == head || be->be_node.prev == head)
614 goto no_merge;
615 prev = list_entry(be->be_node.prev, struct pnfs_block_extent, be_node);
616 if ((prev->be_f_offset + prev->be_length != be->be_f_offset) ||
617 !extents_consistent(prev, be))
618 goto no_merge;
619 _prep_new_extent(storage, prev, prev->be_f_offset,
620 prev->be_length + be->be_length, prev->be_state);
621 list_replace(&prev->be_node, &storage->be_node);
622 bl_put_extent(prev);
623 list_del(&be->be_node);
624 bl_put_extent(be);
625 return storage;
626
627 no_merge:
628 kfree(storage);
629 return be;
630}