]> git.neil.brown.name Git - LaFS.git/blob - block.c
README update, typos, FIXME comments etc. No code.
[LaFS.git] / block.c
1
2 /*
3  * Handle data blocks for LaFS
4  * fs/lafs/block.c
5  * Copyright (C) 2004-2009
6  * NeilBrown <neilb@suse.de>
7  * Released under the GPL, version 2
8  */
9
10 #include        "lafs.h"
11 #include        <linux/buffer_head.h> /* for try_to_release_page */
12 /*
13  * Data blocks are stored in a regular address space for the
14  * relevant file.  A page may have multiple datablocks, but
15  * a datablock cannot extend beyond one page
16  * Each datablock has (or can have) a 'struct datablock' attribute
17  * structure.  These are allocated as an array per page, and attached
18  * at the ->private pointer on the page.
19  *
20  */
21
22 #if DEBUG_REF
23 static DEFINE_SPINLOCK(refl);
24 void add_ref(struct block *b, char *ref, char *file, int line)
25 {
26         int i;
27         int z = -1;
28         spin_lock(&refl);
29         for (i = 0; i < 16; i++) {
30                 if (b->holders[i].cnt) {
31                         if (strcmp(b->holders[i].name, ref) == 0) {
32                                 b->holders[i].cnt++;
33                                 spin_unlock(&refl);
34                                 return;
35                         }
36                 } else
37                         z = i;
38         }
39         if (z < 0) {
40                 spin_unlock(&refl);
41                 printk(KERN_ERR "LaFS: add_ref all holders are in use"
42                        " at %s:%d\nblock: %s\n",
43                        file, line, strblk(b));
44                 BUG();
45         }
46         b->holders[z].cnt = 1;
47         b->holders[z].name = ref;
48         spin_unlock(&refl);
49 }
50
51 void del_ref(struct block *b, char *ref, char *file, int line)
52 {
53         int i;
54         spin_lock(&refl);
55         for (i = 0; i < 16; i++) {
56                 if (b->holders[i].cnt &&
57                     strcmp(b->holders[i].name, ref) == 0) {
58                         b->holders[i].cnt--;
59                         spin_unlock(&refl);
60                         return;
61                 }
62
63         }
64         spin_unlock(&refl);
65         printk(KERN_ERR "LaFS: holder %s not found at %s:%d\nblk: %s\n",
66                ref, file, line, strblk(b));
67         BUG();
68 }
69 #endif
70
71 /* Based on grow_dev_page */
72 struct datablock *
73 lafs_get_block(struct inode *ino, unsigned long index, struct page *p,
74                int gfp, REFARG)
75 {
76         struct datablock *b = NULL;
77         int bits = PAGE_SHIFT - ino->i_blkbits;
78         int unlock = !p;
79         if (!p) {
80                 p = find_get_page(&ino->i_data, index >> bits);
81                 if (p) {
82                         spin_lock(&ino->i_data.private_lock);
83                         if (PagePrivate(p)) {
84                                 b = (struct datablock *)p->private;
85                                 b += index & ((1<<bits)-1);
86                                 getdref_locked(b, REF);
87                         }
88                         spin_unlock(&ino->i_data.private_lock);
89                         page_cache_release(p);
90                         p = NULL;
91                 }
92                 if (b)
93                         return b;
94         }
95         if (!p)
96                 p = find_or_create_page(&ino->i_data, index>>bits, gfp);
97         if (!p) {
98                 dprintk("find or create returned NULL\n");
99                 return NULL;
100         }
101
102         if (!PagePrivate(p)) {
103
104                 unsigned long ind = p->index << bits;
105                 int i;
106                 /* New page, need to set up attribute blocks */
107                 /* FIXME use kmem_cache */
108                 dprintk("setting up %p for %lu\n", p, index);
109                 b = kzalloc(sizeof(struct datablock)<<bits, gfp);
110                 if (!b) {
111                         if (unlock)
112                                 unlock_page(p);
113                         page_cache_release(p);
114                         return NULL;
115                 }
116
117                 for (i = 0; i < (1<<bits); i++) {
118                         b[i].page = p;
119                         atomic_set(&b[i].b.refcnt, 0);
120                         b[i].b.flags = 0;
121                         b[i].b.fileaddr = ind++;
122                         b[i].b.inode = ino;
123                         b[i].b.physaddr = 0;
124                         b[i].b.parent = NULL;
125                         INIT_LIST_HEAD(&b[i].b.siblings);
126                         INIT_LIST_HEAD(&b[i].b.lru);
127                         INIT_LIST_HEAD(&b[i].b.peers);
128                         INIT_LIST_HEAD(&b[i].orphans);
129                         INIT_LIST_HEAD(&b[i].cleaning);
130                         b[i].b.chain = NULL;
131
132                         b[i].my_inode = NULL;
133
134                         /* FIXME what else needs to be initialised? */
135                 }
136
137                 spin_lock(&ino->i_data.private_lock);
138                 if (!PagePrivate(p)) {
139                         p->private = (unsigned long) b;
140                         SetPagePrivate(p);
141                         b = NULL;
142                 }
143                 spin_unlock(&ino->i_data.private_lock);
144                 kfree(b);
145         }
146
147         b = (struct datablock *)p->private;
148         b += index & ((1<<bits)-1);
149         getdref_locked(b, REF);
150
151         if (unlock) {
152                 unlock_page(p);
153                 page_cache_release(p);
154         }
155         LAFS_BUG(b->b.inode != ino, &b->b);
156         return b;
157 }
158
159 /* When a page is truncated, either because the file is being
160  * truncated or because the page is being removed from the
161  * mapping, invalidate_page is called to clean up any
162  * ->private content.
163  * If (and only if) offset == 0, we should discard the ->private
164  * content and clear the PagePrivate flag.  This is done by calling
165  * try_to_release_page which calls our lafs_release_page (if there
166  * is no pending writeback).
167  *
168  * If any blocks are beyond the end of the (i_size), they should
169  * be erased.
170  */
171
172 void lafs_invalidate_page(struct page *page, unsigned long offset)
173 {
174         struct inode *ino = page->mapping->host;
175         struct super_block *sb = ino->i_sb;
176         int bits = PAGE_SHIFT - sb->s_blocksize_bits;
177         loff_t size = i_size_read(ino);
178         loff_t start = (loff_t)page_index(page) << PAGE_SHIFT;
179
180         if (PagePrivate(page)) {
181                 int i;
182                 int b_start = 0;
183                 struct datablock *b = (struct datablock *)page->private;
184
185                 /* We need to:
186                  *   erase any blocks beyond end-of-file
187                  *   wait for any pending IO to complete (so page can be freed)
188                  */
189                 for (i = 0; i < (1<<bits); i++) {
190                         if (LAFSI(ino)->type >= TypeBase && start >= size)
191                                 /* Remove block from mapping and file */
192                                 lafs_erase_dblock(&b[i]);
193                         else if (b_start >= offset) {
194                                 /* Just remove block from mapping */
195                                 lafs_iolock_written(&b[i].b);
196                                 LAFS_BUG(test_bit(B_Dirty, &b[i].b.flags),
197                                          &b[i].b);
198                                 LAFS_BUG(test_bit(B_Realloc, &b[i].b.flags),
199                                          &b[i].b);
200                                 clear_bit(B_Valid, &b[i].b.flags);
201                                 lafs_iounlock_block(&b[i].b);
202                         }
203                         b_start += sb->s_blocksize;
204                         start += sb->s_blocksize;
205                         LAFS_BUG(offset == 0 &&
206                                  test_bit(B_IOLock, &b[i].b.flags),
207                                  &b[i].b);
208                 }
209         }
210         if (offset == 0) {
211                 int success = try_to_release_page(page, 0);
212                 BUG_ON(!success);
213         }
214 }
215
216 int lafs_release_page(struct page *page, gfp_t gfp_flags)
217 {
218         struct address_space * const mapping = page->mapping;
219         int bits = PAGE_SHIFT - mapping->host->i_blkbits;
220         int i;
221         int credits = 0;
222         struct indexblock *parents[1<<bits];
223         struct datablock *b = NULL;
224
225         if (PageWriteback(page)) {
226                 BUG(); /* testing - remove this later */
227                 return 0;
228         }
229
230         spin_lock(&mapping->private_lock);
231         if (!PagePrivate(page)) {
232                 spin_unlock(&mapping->private_lock);
233                 return 1;
234         }
235
236         /* based on try_to_free_buffers, we need to
237          * - pass any write errors back up to page
238          * - mark the page clean if the buffers are all clean
239          * - fail if any buffers are busy (pinned, or dirty)
240          * - free the data structures
241          */
242         b = (struct datablock *)page->private;
243         for (i = 0; i < (1<<bits); i++) {
244                 if (test_bit(B_WriteError, &b[i].b.flags))
245                         set_bit(AS_EIO, &mapping->flags);
246                 if (test_bit(B_Dirty, &b[i].b.flags) ||
247                     test_bit(B_Pinned, &b[i].b.flags) ||
248                     test_bit(B_IOLock, &b[i].b.flags) ||
249                     test_bit(B_Writeback, &b[i].b.flags)
250                     /* NOTE: if we find an Uninc is set when we
251                      * need to invalidate the page, then we
252                      * should be waiting for all pages to be gone
253                      * properly before allowing truncate to complete.
254                      * The whole file doesn't need to be truncated yet,
255                      * that can continue lazily. but all the pages must
256                      * be incorporated.  Maybe we just need to
257                      * wait for a checkpoint here.??
258                      */
259                     || test_bit(B_Uninc, &b[i].b.flags)
260                         ) {
261                         spin_unlock(&mapping->private_lock);
262                         LAFS_BUG(1, &b[i].b);
263                         /* This not really a bug, but bugs can lead
264                          * here, and this is an unusual situation
265                          * (currently) so we BUG here to be safe.
266                          * When we find a situation that does fail a
267                          * release_page with good reason, we should
268                          * remove this BUG().
269                          */
270                         return 0;
271                 }
272         }
273         /* OK, we are good to go. */
274         for (i = 0; i < (1<<bits); i++) {
275                 parents[i] = b[i].b.parent;
276                 b[i].b.parent = NULL;
277                 list_del_init(&b[i].b.siblings);
278                 list_del_init(&b[i].b.lru);
279                 list_del_init(&b[i].b.peers);
280                 (void)getdref_locked(&b[i], MKREF(lafs_release));
281                 if (test_and_clear_bit(B_Credit, &b[i].b.flags))
282                         credits++;
283                 if (test_and_clear_bit(B_ICredit, &b[i].b.flags))
284                         credits++;
285                 if (test_and_clear_bit(B_NCredit, &b[i].b.flags))
286                         credits++;
287                 if (test_and_clear_bit(B_NICredit, &b[i].b.flags))
288                         credits++;
289                 /* When !PagePrivate(page), && refcnt, we hold a ref on the
290                  * first block which holds a ref on the page.
291                  * When ref on firstblock with !PagePrivate(page) becomes zero,
292                  * we free
293                  */
294                 if (i)
295                         getdref_locked(&b[0], MKREF(lafs_release_0));
296                 else
297                         get_page(page);
298         }
299
300         page->private = 0;
301         ClearPagePrivate(page);
302
303         spin_unlock(&mapping->private_lock);
304         lafs_space_return(fs_from_inode(mapping->host), credits);
305
306         for (i = 0; i < (1<<bits); i++) {
307                 putdref(&b[i], MKREF(lafs_release));
308                 putiref(parents[i], MKREF(child));
309         }
310
311         return 1;
312 }
313
314 /* Pinning and dirtying of datablocks.
315  * Before a modification of a datablock can be allowed we must be sure there
316  * will be room to write it out.  Thus suitable pre-allocations are required.
317  * There are two general cases to consider.
318  * In one case we are building an internal transaction such as a directory
319  * update.  In this case we need to pre-allocated for all blocks that might
320  * be updated and if those preallocations succeed, we make the update
321  * and mark the blocks as dirty.  They are also 'pinned' and will be written
322  * as part of the current phase.
323  * In the other case we are simply writing a single block for user-space.
324  * In this case the preallocation is still required, but the block is not
325  * pinned to the phase and so may be written out at any time.
326  * We have a series of functions that help manage this.  They are:
327  * lafs_setparent.
328  *   This ensures that all parents are loaded in memory and ref-counted
329  *   by the target block.
330  * lafs_reserve
331  *   This takes a block with parents and attempts to reserve space for writing
332  *   out all of the parents. and the block.  This may block or fail if space
333  *   is tight.
334  * lafs_pin_block
335  *   This takes a reserved block and pins it to the current phase.
336  * lafs_dirty_dblock
337  *   This takes a reserved (possibly pinned) block and marks it dirty.
338  */
339
340 /* pinning a block ensures that we can write to it.
341  * If the block does not already have an allocation
342  * (i.e. a physical address) then we are allowed to
343  * fail -ENOSPC.  Otherwise we can at most wait
344  * a while.
345  * The update may not occur for a long time, so
346  * the reservations must be preserved across
347  * multiple checkpoints (unlikely but possible).
348  * So each pinning is counted and reserves whatever
349  * is required.  When a pin is released the reserved
350  * space is given to the block if it needs it, or
351  * is returned to the filesystem.
352  */
353
354 int
355 lafs_reserve_block(struct block *b, int alloc_type)
356 {
357         int err = 0;
358         struct fs *fs = fs_from_inode(b->inode);
359
360         if (!test_bit(B_PhysValid, &b->flags))
361                 b->physaddr = 0;
362
363         if (test_bit(B_Index, &b->flags))
364                 LAFS_BUG(b->parent == NULL && !test_bit(B_Root, &b->flags),
365                          b);
366         else
367                 err = lafs_setparent(dblk(b));
368
369         /* If there is already a physaddr, or the data is
370          * stored in the inode, then we aren't really allocating
371          * new space.
372          * When unlinking from a small directory, this can
373          * be an issue.
374          */
375         if (alloc_type == NewSpace &&
376             (b->physaddr || (b->fileaddr == 0
377                              && LAFSI(b->inode)->depth == 0)))
378                 alloc_type = ReleaseSpace;
379
380         if (alloc_type == NewSpace && test_bit(B_InoIdx, &b->flags))
381                 /* physaddr isn't necessarily set for the InoIdx block.
382                  */
383                 alloc_type = ReleaseSpace;
384
385         /* Allocate space in the filesystem */
386         err = err ?: lafs_prealloc(b, alloc_type);
387
388         /* Allocate space in the file (and quota set) */
389         if (err == 0 && b->physaddr == 0 &&
390             !test_bit(B_Index, &b->flags) &&
391             !test_and_set_bit(B_Prealloc, &b->flags)) {
392                 err = lafs_summary_allocate(fs, b->inode, 1);
393                 if (err)
394                         clear_bit(B_Prealloc, &b->flags);
395         }
396
397         /* Having reserved the block, we need to get a segref,
398          * which will involve reserving those blocks too.
399          * However we never get a segref for Root.
400          */
401
402         while (err == 0
403                && !test_bit(B_Root, &b->flags)
404                && !test_bit(B_SegRef, &b->flags))
405                 err = lafs_seg_ref_block(b, 0);
406
407         if (err == 0)
408                 return 0;
409         /* FIXME maybe CleanSpace should return -EAGAIN if there
410          * is a good chance that the cleaner will help out soon??
411          * I wonder how "soon" can be defined.
412          */
413         if (alloc_type == CleanSpace || alloc_type == NewSpace)
414                 return -ENOSPC;
415         if (alloc_type == ReleaseSpace)
416                 return -EAGAIN;
417         LAFS_BUG(1, b);
418 }
419
420 int
421 lafs_pin_dblock(struct datablock *b, int alloc_type)
422 {
423         /* We need to:
424          * - pin parents and inode
425          * - preallocate as needed
426          * - reference the old segment
427          * - update flags and pointers.
428          */
429         /* FIXME I probably need an iolock here to avoid racing with
430          * lafs_cluster_allocate which can clear dirty and so lose credits.
431          */
432         int err;
433         struct fs *fs = fs_from_inode(b->b.inode);
434         struct block *blk;
435
436         /* We don't pin a datablock of an inode if there is an
437          * InoIdx block. We pin the InoIdx block instead.
438          * They might both be pinned at the same time, but
439          * only when the index block has swapped phase and the
440          * data block is waiting to be written.
441          */
442         if (LAFSI(b->b.inode)->type == TypeInodeFile &&
443             b->my_inode &&
444             LAFSI(b->my_inode)->iblock) {
445                 struct indexblock *ib = lafs_make_iblock(b->my_inode, ADOPT, SYNC,
446                                                          MKREF(pindb));
447                 if (IS_ERR(ib))
448                         blk = getref(&b->b, MKREF(pindb));
449                 else
450                         blk = &ib->b;
451         } else
452                 blk = getref(&b->b, MKREF(pindb));
453
454         LAFS_BUG(!test_phase_locked(fs), &b->b);
455
456         lafs_phase_wait(blk);
457
458         set_bit(B_PinPending, &b->b.flags);
459         err = lafs_reserve_block(blk, alloc_type);
460
461         if (err) {
462                 clear_bit(B_PinPending, &b->b.flags);
463                 putref(blk, MKREF(pindb));
464                 return err;
465         }
466
467         lafs_pin_block(blk);
468         putref(blk, MKREF(pindb));
469         return 0;
470 }
471
472 /* lafs_dirty_dblock
473  * This cannot fail.  The block is already 'pinned' for writing
474  * so any preallocations and other checks have passed.
475  */
476 void
477 lafs_dirty_dblock(struct datablock *b)
478 {
479         LAFS_BUG(!test_bit(B_Valid, &b->b.flags), &b->b);
480         if (test_bit(B_Pinned, &b->b.flags))
481                 b->b.inode->i_sb->s_dirt = 1;
482         /*
483          * FIXME maybe check we aren't dirtying a dirty block
484          * in the previous phase.
485          */
486
487         if (!test_and_set_bit(B_Dirty, &b->b.flags)) {
488                 if (!test_and_clear_bit(B_Credit, &b->b.flags))
489                         if (!test_and_clear_bit(B_NCredit, &b->b.flags))
490                                 LAFS_BUG(1, &b->b); // Credit should have been set.
491                 __set_page_dirty_nobuffers(b->page);
492         }
493         if (!test_and_set_bit(B_UnincCredit, &b->b.flags))
494                 if (!test_and_clear_bit(B_ICredit, &b->b.flags))
495                         if (!test_and_clear_bit(B_NICredit, &b->b.flags))
496                                 LAFS_BUG(1, &b->b);     // ICredit should be set before we dirty
497                                         // a block.
498
499         // FIXME Do I need to do something with PinPending??
500
501 }
502
503 void
504 lafs_erase_dblock(struct datablock *b)
505 {
506         struct fs *fs = fs_from_inode(b->b.inode);
507
508         dprintk("Eraseblock for %s\n", strblk(&b->b));
509         lafs_iolock_written(&b->b);
510         if (b->b.physaddr == 0 &&
511             b->b.fileaddr == 0 &&
512             LAFSI(b->b.inode)->depth == 0) {
513                 /* We need to clear out the index block that this
514                  * block lives in.
515                  * Need private_lock to be allowed to dereference ->iblock
516                  * though if b was dirty we shouldn't.... FIXME.
517                  */
518                 struct indexblock *ib;
519                 spin_lock(&b->b.inode->i_data.private_lock);
520                 ib = LAFSI(b->b.inode)->iblock;
521                 if (ib)
522                         getiref_locked(ib, MKREF("erasedblock"));
523                 spin_unlock(&b->b.inode->i_data.private_lock);
524                 if (ib) {
525                         lafs_iolock_written(&ib->b);
526                         if (ib->depth == 0) {
527                                 LAFS_BUG(LAFSI(b->b.inode)->depth !=
528                                          ib->depth, &b->b);
529                                 lafs_clear_index(ib);
530                                 clear_bit(B_PhysValid, &b->b.flags);
531                         }
532                         lafs_iounlock_block(&ib->b);
533                         putiref(ib, MKREF("erasedblock"));
534                 }
535         }
536
537         if (LAFSI(b->b.inode)->type == TypeInodeFile &&
538             LAFSI(b->my_inode)->iblock)
539                 LAFS_BUG(LAFSI(b->my_inode)->iblock->depth > 1,
540                          &b->b);
541
542         clear_bit(B_Valid, &b->b.flags);
543         lafs_unclean(b);
544         if (test_and_clear_bit(B_Dirty, &b->b.flags))
545                 lafs_space_return(fs, 1);
546         if (test_and_clear_bit(B_Realloc, &b->b.flags))
547                 lafs_space_return(fs, 1);
548         if (test_and_clear_bit(B_Prealloc, &b->b.flags))
549                 if (b->b.physaddr == 0)
550                         lafs_summary_allocate(fs, b->b.inode, -1);
551
552         spin_lock(&fs->lock);
553         if (test_bit(B_Pinned, &b->b.flags)) {
554                 /* When erasing a pinned dblock it will usually be on a
555                  * leaf list, so we must remove it.
556                  * However it is IOLocked so it might not be on the leaf list.
557                  */
558                 int onlru = 0;
559                 LAFS_BUG(test_bit(B_Writeback, &b->b.flags), &b->b);
560                 if (!list_empty(&b->b.lru)) {
561                         onlru = 1;
562                         list_del_init(&b->b.lru);
563                 }
564                 if (!test_bit(B_Root, &b->b.flags))
565                         atomic_dec(&b->b.parent->pincnt
566                                    [!!test_bit(B_Phase1, &b->b.flags)]);
567                 clear_bit(B_Pinned, &b->b.flags);
568                 spin_unlock(&fs->lock);
569                 if (!test_bit(B_Root, &b->b.flags))
570                         lafs_refile(&b->b.parent->b, 0);
571                 if (onlru)
572                         putiref(b, MKREF(leaf));
573         } else
574                 spin_unlock(&fs->lock);
575
576         /* we set Writeback to validate the call to lafs_allocated block */
577         set_bit(B_Writeback, &b->b.flags);
578         lafs_iounlock_block(&b->b);
579         if (b->b.parent == NULL)
580                 /* Erasing a block that isn't in the indexing tree only
581                  * happens when truncating and lafs_invalidate_page is called
582                  * on some clean page.
583                  * So we don't clear out physaddr here, but instead leave that
584                  * to the core truncate code.
585                  * Just remove B_PhysValid to avoid confusion.
586                  */
587                 clear_bit(B_PhysValid, &b->b.flags);
588         else if (b->b.physaddr)
589                 lafs_allocated_block(fs, &b->b, 0);
590         else
591                 if (test_and_clear_bit(B_UnincCredit, &b->b.flags))
592                         lafs_space_return(fs, 1);
593         lafs_writeback_done(&b->b);
594 }
595
596 void
597 lafs_dirty_iblock(struct indexblock *b)
598 {
599
600         /* FIXME is this all I have to do here?
601          * Do I need to put it on a list, or lock or something?
602
603          * Note, only need to set that phase if locked.
604          * Then no-one may change it while in phase transition.
605          * FIXME maybe check we aren't dirtying a dirty block
606          * in the previous phase.
607          */
608
609         LAFS_BUG(!test_bit(B_Pinned, &b->b.flags), &b->b);
610         if (!test_and_set_bit(B_Dirty, &b->b.flags)) {
611                 if (!test_and_clear_bit(B_Credit, &b->b.flags)) {
612                         printk(KERN_ERR "Why have I no credits?\n");
613                         LAFS_BUG(1, &b->b); // Credit should have been set.
614                 }
615         }
616
617         /* Iblocks don't always have ICredits.  If they have room
618          * for 3 new addresses, the ICredit is not essential.  But
619          * it is preferred.
620          */
621         if (!test_bit(B_UnincCredit, &b->b.flags))
622                 /* We would like a credit */
623                 if (test_and_clear_bit(B_ICredit, &b->b.flags))
624                         /* We have a credit */
625                         if (test_and_set_bit(B_UnincCredit, &b->b.flags))
626                                 /* race - we didn't need it after all */
627                                 lafs_space_return(fs_from_inode(b->b.inode), 1);
628
629         b->b.inode->i_sb->s_dirt = 1;
630 }