Merge from vendor branch LIBARCHIVE:
[dragonfly.git] / sys / vfs / hammer / hammer_blockmap.c
1 /*
2  * Copyright (c) 2008 The DragonFly Project.  All rights reserved.
3  * 
4  * This code is derived from software contributed to The DragonFly Project
5  * by Matthew Dillon <dillon@backplane.com>
6  * 
7  * Redistribution and use in source and binary forms, with or without
8  * modification, are permitted provided that the following conditions
9  * are met:
10  * 
11  * 1. Redistributions of source code must retain the above copyright
12  *    notice, this list of conditions and the following disclaimer.
13  * 2. Redistributions in binary form must reproduce the above copyright
14  *    notice, this list of conditions and the following disclaimer in
15  *    the documentation and/or other materials provided with the
16  *    distribution.
17  * 3. Neither the name of The DragonFly Project nor the names of its
18  *    contributors may be used to endorse or promote products derived
19  *    from this software without specific, prior written permission.
20  * 
21  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
24  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE
25  * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
26  * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING,
27  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
28  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
29  * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
30  * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
31  * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
32  * SUCH DAMAGE.
33  * 
34  * $DragonFly: src/sys/vfs/hammer/hammer_blockmap.c,v 1.23 2008/07/03 04:24:51 dillon Exp $
35  */
36
37 /*
38  * HAMMER blockmap
39  */
40 #include "hammer.h"
41
42 static int hammer_res_rb_compare(hammer_reserve_t res1, hammer_reserve_t res2);
43 static int hammer_reserve_setdelay(hammer_mount_t hmp, hammer_reserve_t resv,
44                         hammer_off_t zone2_offset);
45
46
47 /*
48  * Reserved big-blocks red-black tree support
49  */
50 RB_GENERATE2(hammer_res_rb_tree, hammer_reserve, rb_node,
51              hammer_res_rb_compare, hammer_off_t, zone_offset);
52
53 static int
54 hammer_res_rb_compare(hammer_reserve_t res1, hammer_reserve_t res2)
55 {
56         if (res1->zone_offset < res2->zone_offset)
57                 return(-1);
58         if (res1->zone_offset > res2->zone_offset)
59                 return(1);
60         return(0);
61 }
62
63 /*
64  * Allocate bytes from a zone
65  */
66 hammer_off_t
67 hammer_blockmap_alloc(hammer_transaction_t trans, int zone,
68                       int bytes, int *errorp)
69 {
70         hammer_mount_t hmp;
71         hammer_volume_t root_volume;
72         hammer_blockmap_t blockmap;
73         hammer_blockmap_t freemap;
74         hammer_reserve_t resv;
75         struct hammer_blockmap_layer1 *layer1;
76         struct hammer_blockmap_layer2 *layer2;
77         hammer_buffer_t buffer1 = NULL;
78         hammer_buffer_t buffer2 = NULL;
79         hammer_buffer_t buffer3 = NULL;
80         hammer_off_t tmp_offset;
81         hammer_off_t next_offset;
82         hammer_off_t result_offset;
83         hammer_off_t layer1_offset;
84         hammer_off_t layer2_offset;
85         hammer_off_t base_off;
86         int loops = 0;
87         int offset;             /* offset within big-block */
88
89         hmp = trans->hmp;
90
91         /*
92          * Deal with alignment and buffer-boundary issues.
93          *
94          * Be careful, certain primary alignments are used below to allocate
95          * new blockmap blocks.
96          */
97         bytes = (bytes + 15) & ~15;
98         KKASSERT(bytes > 0 && bytes <= HAMMER_XBUFSIZE);
99         KKASSERT(zone >= HAMMER_ZONE_BTREE_INDEX && zone < HAMMER_MAX_ZONES);
100
101         /*
102          * Setup
103          */
104         root_volume = trans->rootvol;
105         *errorp = 0;
106         blockmap = &hmp->blockmap[zone];
107         freemap = &hmp->blockmap[HAMMER_ZONE_FREEMAP_INDEX];
108         KKASSERT(HAMMER_ZONE_DECODE(blockmap->next_offset) == zone);
109
110         next_offset = blockmap->next_offset;
111 again:
112         /*
113          * Check for wrap
114          */
115         if (next_offset == HAMMER_ZONE_ENCODE(zone + 1, 0)) {
116                 if (++loops == 2) {
117                         result_offset = 0;
118                         *errorp = ENOSPC;
119                         goto failed;
120                 }
121                 next_offset = HAMMER_ZONE_ENCODE(zone, 0);
122         }
123
124         /*
125          * The allocation request may not cross a buffer boundary.  Special
126          * large allocations must not cross a large-block boundary.
127          */
128         tmp_offset = next_offset + bytes - 1;
129         if (bytes <= HAMMER_BUFSIZE) {
130                 if ((next_offset ^ tmp_offset) & ~HAMMER_BUFMASK64) {
131                         next_offset = tmp_offset & ~HAMMER_BUFMASK64;
132                         goto again;
133                 }
134         } else {
135                 if ((next_offset ^ tmp_offset) & ~HAMMER_LARGEBLOCK_MASK64) {
136                         next_offset = tmp_offset & ~HAMMER_LARGEBLOCK_MASK64;
137                         goto again;
138                 }
139         }
140         offset = (int)next_offset & HAMMER_LARGEBLOCK_MASK;
141
142         /*
143          * Dive layer 1.
144          */
145         layer1_offset = freemap->phys_offset +
146                         HAMMER_BLOCKMAP_LAYER1_OFFSET(next_offset);
147         layer1 = hammer_bread(hmp, layer1_offset, errorp, &buffer1);
148         KKASSERT(*errorp == 0);
149
150         /*
151          * Check CRC.
152          */
153         if (layer1->layer1_crc != crc32(layer1, HAMMER_LAYER1_CRCSIZE)) {
154                 Debugger("CRC FAILED: LAYER1");
155         }
156
157         /*
158          * If we are at a big-block boundary and layer1 indicates no 
159          * free big-blocks, then we cannot allocate a new bigblock in
160          * layer2, skip to the next layer1 entry.
161          */
162         if (offset == 0 && layer1->blocks_free == 0) {
163                 next_offset = (next_offset + HAMMER_BLOCKMAP_LAYER2) &
164                               ~HAMMER_BLOCKMAP_LAYER2_MASK;
165                 goto again;
166         }
167         KKASSERT(layer1->phys_offset != HAMMER_BLOCKMAP_UNAVAIL);
168
169         /*
170          * Dive layer 2, each entry represents a large-block.
171          */
172         layer2_offset = layer1->phys_offset +
173                         HAMMER_BLOCKMAP_LAYER2_OFFSET(next_offset);
174         layer2 = hammer_bread(hmp, layer2_offset, errorp, &buffer2);
175         KKASSERT(*errorp == 0);
176
177         /*
178          * Check CRC.
179          */
180         if (layer2->entry_crc != crc32(layer2, HAMMER_LAYER2_CRCSIZE)) {
181                 Debugger("CRC FAILED: LAYER2");
182         }
183
184         /*
185          * Skip the layer if the zone is owned by someone other then us.
186          */
187         if (layer2->zone && layer2->zone != zone) {
188                 next_offset += (HAMMER_LARGEBLOCK_SIZE - offset);
189                 goto again;
190         }
191         if (offset < layer2->append_off) {
192                 next_offset += layer2->append_off - offset;
193                 goto again;
194         }
195
196         /*
197          * We need the lock from this point on.  We have to re-check zone
198          * ownership after acquiring the lock and also check for reservations.
199          */
200         hammer_lock_ex(&hmp->blkmap_lock);
201
202         if (layer2->zone && layer2->zone != zone) {
203                 hammer_unlock(&hmp->blkmap_lock);
204                 next_offset += (HAMMER_LARGEBLOCK_SIZE - offset);
205                 goto again;
206         }
207         if (offset < layer2->append_off) {
208                 hammer_unlock(&hmp->blkmap_lock);
209                 next_offset += layer2->append_off - offset;
210                 goto again;
211         }
212
213         /*
214          * The bigblock might be reserved by another zone.  If it is reserved
215          * by our zone we may have to move next_offset past the append_off.
216          */
217         base_off = (next_offset &
218                     (~HAMMER_LARGEBLOCK_MASK64 & ~HAMMER_OFF_ZONE_MASK)) | 
219                     HAMMER_ZONE_RAW_BUFFER;
220         resv = RB_LOOKUP(hammer_res_rb_tree, &hmp->rb_resv_root, base_off);
221         if (resv) {
222                 if (resv->zone != zone) {
223                         hammer_unlock(&hmp->blkmap_lock);
224                         next_offset = (next_offset + HAMMER_LARGEBLOCK_SIZE) &
225                                       ~HAMMER_LARGEBLOCK_MASK64;
226                         goto again;
227                 }
228                 if (offset < resv->append_off) {
229                         hammer_unlock(&hmp->blkmap_lock);
230                         next_offset += resv->append_off - offset;
231                         goto again;
232                 }
233         }
234
235         /*
236          * Ok, we can allocate out of this layer2 big-block.  Assume ownership
237          * of the layer for real.  At this point we've validated any
238          * reservation that might exist and can just ignore resv.
239          */
240         if (layer2->zone == 0) {
241                 /*
242                  * Assign the bigblock to our zone
243                  */
244                 hammer_modify_buffer(trans, buffer1,
245                                      layer1, sizeof(*layer1));
246                 --layer1->blocks_free;
247                 layer1->layer1_crc = crc32(layer1,
248                                            HAMMER_LAYER1_CRCSIZE);
249                 hammer_modify_buffer_done(buffer1);
250                 hammer_modify_buffer(trans, buffer2,
251                                      layer2, sizeof(*layer2));
252                 layer2->zone = zone;
253                 KKASSERT(layer2->bytes_free == HAMMER_LARGEBLOCK_SIZE);
254                 KKASSERT(layer2->append_off == 0);
255                 hammer_modify_volume_field(trans, trans->rootvol,
256                                            vol0_stat_freebigblocks);
257                 --root_volume->ondisk->vol0_stat_freebigblocks;
258                 hmp->copy_stat_freebigblocks =
259                         root_volume->ondisk->vol0_stat_freebigblocks;
260                 hammer_modify_volume_done(trans->rootvol);
261         } else {
262                 hammer_modify_buffer(trans, buffer2,
263                                      layer2, sizeof(*layer2));
264         }
265         KKASSERT(layer2->zone == zone);
266
267         layer2->bytes_free -= bytes;
268         KKASSERT(layer2->append_off <= offset);
269         layer2->append_off = offset + bytes;
270         layer2->entry_crc = crc32(layer2, HAMMER_LAYER2_CRCSIZE);
271         hammer_modify_buffer_done(buffer2);
272         KKASSERT(layer2->bytes_free >= 0);
273
274         if (resv) {
275                 KKASSERT(resv->append_off <= offset);
276                 resv->append_off = offset + bytes;
277         }
278
279         /*
280          * If we are allocating from the base of a new buffer we can avoid
281          * a disk read by calling hammer_bnew().
282          */
283         if ((next_offset & HAMMER_BUFMASK) == 0) {
284                 hammer_bnew_ext(trans->hmp, next_offset, bytes,
285                                 errorp, &buffer3);
286         }
287         result_offset = next_offset;
288
289         /*
290          * Process allocated result_offset
291          */
292         hammer_modify_volume(NULL, root_volume, NULL, 0);
293         blockmap->next_offset = next_offset + bytes;
294         hammer_modify_volume_done(root_volume);
295         hammer_unlock(&hmp->blkmap_lock);
296 failed:
297
298         /*
299          * Cleanup
300          */
301         if (buffer1)
302                 hammer_rel_buffer(buffer1, 0);
303         if (buffer2)
304                 hammer_rel_buffer(buffer2, 0);
305         if (buffer3)
306                 hammer_rel_buffer(buffer3, 0);
307
308         return(result_offset);
309 }
310
311 /*
312  * Frontend function - Reserve bytes in a zone.
313  *
314  * This code reserves bytes out of a blockmap without committing to any
315  * meta-data modifications, allowing the front-end to directly issue disk
316  * write I/O for large blocks of data
317  *
318  * The backend later finalizes the reservation with hammer_blockmap_finalize()
319  * upon committing the related record.
320  */
321 hammer_reserve_t
322 hammer_blockmap_reserve(hammer_mount_t hmp, int zone, int bytes,
323                         hammer_off_t *zone_offp, int *errorp)
324 {
325         hammer_volume_t root_volume;
326         hammer_blockmap_t blockmap;
327         hammer_blockmap_t freemap;
328         struct hammer_blockmap_layer1 *layer1;
329         struct hammer_blockmap_layer2 *layer2;
330         hammer_buffer_t buffer1 = NULL;
331         hammer_buffer_t buffer2 = NULL;
332         hammer_buffer_t buffer3 = NULL;
333         hammer_off_t tmp_offset;
334         hammer_off_t next_offset;
335         hammer_off_t layer1_offset;
336         hammer_off_t layer2_offset;
337         hammer_off_t base_off;
338         hammer_reserve_t resv;
339         hammer_reserve_t resx;
340         int loops = 0;
341         int offset;
342
343         /*
344          * Setup
345          */
346         KKASSERT(zone >= HAMMER_ZONE_BTREE_INDEX && zone < HAMMER_MAX_ZONES);
347         root_volume = hammer_get_root_volume(hmp, errorp);
348         if (*errorp)
349                 return(NULL);
350         blockmap = &hmp->blockmap[zone];
351         freemap = &hmp->blockmap[HAMMER_ZONE_FREEMAP_INDEX];
352         KKASSERT(HAMMER_ZONE_DECODE(blockmap->next_offset) == zone);
353
354         /*
355          * Deal with alignment and buffer-boundary issues.
356          *
357          * Be careful, certain primary alignments are used below to allocate
358          * new blockmap blocks.
359          */
360         bytes = (bytes + 15) & ~15;
361         KKASSERT(bytes > 0 && bytes <= HAMMER_XBUFSIZE);
362
363         next_offset = blockmap->next_offset;
364 again:
365         resv = NULL;
366         /*
367          * Check for wrap
368          */
369         if (next_offset == HAMMER_ZONE_ENCODE(zone + 1, 0)) {
370                 if (++loops == 2) {
371                         *errorp = ENOSPC;
372                         goto failed;
373                 }
374                 next_offset = HAMMER_ZONE_ENCODE(zone, 0);
375         }
376
377         /*
378          * The allocation request may not cross a buffer boundary.  Special
379          * large allocations must not cross a large-block boundary.
380          */
381         tmp_offset = next_offset + bytes - 1;
382         if (bytes <= HAMMER_BUFSIZE) {
383                 if ((next_offset ^ tmp_offset) & ~HAMMER_BUFMASK64) {
384                         next_offset = tmp_offset & ~HAMMER_BUFMASK64;
385                         goto again;
386                 }
387         } else {
388                 if ((next_offset ^ tmp_offset) & ~HAMMER_LARGEBLOCK_MASK64) {
389                         next_offset = tmp_offset & ~HAMMER_LARGEBLOCK_MASK64;
390                         goto again;
391                 }
392         }
393         offset = (int)next_offset & HAMMER_LARGEBLOCK_MASK;
394
395         /*
396          * Dive layer 1.
397          */
398         layer1_offset = freemap->phys_offset +
399                         HAMMER_BLOCKMAP_LAYER1_OFFSET(next_offset);
400         layer1 = hammer_bread(hmp, layer1_offset, errorp, &buffer1);
401         KKASSERT(*errorp == 0);
402
403         /*
404          * Check CRC.
405          */
406         if (layer1->layer1_crc != crc32(layer1, HAMMER_LAYER1_CRCSIZE)) {
407                 Debugger("CRC FAILED: LAYER1");
408         }
409
410         /*
411          * If we are at a big-block boundary and layer1 indicates no 
412          * free big-blocks, then we cannot allocate a new bigblock in
413          * layer2, skip to the next layer1 entry.
414          */
415         if ((next_offset & HAMMER_LARGEBLOCK_MASK) == 0 &&
416             layer1->blocks_free == 0) {
417                 next_offset = (next_offset + HAMMER_BLOCKMAP_LAYER2) &
418                               ~HAMMER_BLOCKMAP_LAYER2_MASK;
419                 goto again;
420         }
421         KKASSERT(layer1->phys_offset != HAMMER_BLOCKMAP_UNAVAIL);
422
423         /*
424          * Dive layer 2, each entry represents a large-block.
425          */
426         layer2_offset = layer1->phys_offset +
427                         HAMMER_BLOCKMAP_LAYER2_OFFSET(next_offset);
428         layer2 = hammer_bread(hmp, layer2_offset, errorp, &buffer2);
429         KKASSERT(*errorp == 0);
430
431         /*
432          * Check CRC if not allocating into uninitialized space (which we
433          * aren't when reserving space).
434          */
435         if (layer2->entry_crc != crc32(layer2, HAMMER_LAYER2_CRCSIZE)) {
436                 Debugger("CRC FAILED: LAYER2");
437         }
438
439         /*
440          * Skip the layer if the zone is owned by someone other then us.
441          */
442         if (layer2->zone && layer2->zone != zone) {
443                 next_offset += (HAMMER_LARGEBLOCK_SIZE - offset);
444                 goto again;
445         }
446         if (offset < layer2->append_off) {
447                 next_offset += layer2->append_off - offset;
448                 goto again;
449         }
450
451         /*
452          * We need the lock from this point on.  We have to re-check zone
453          * ownership after acquiring the lock and also check for reservations.
454          */
455         hammer_lock_ex(&hmp->blkmap_lock);
456
457         if (layer2->zone && layer2->zone != zone) {
458                 hammer_unlock(&hmp->blkmap_lock);
459                 next_offset += (HAMMER_LARGEBLOCK_SIZE - offset);
460                 goto again;
461         }
462         if (offset < layer2->append_off) {
463                 hammer_unlock(&hmp->blkmap_lock);
464                 next_offset += layer2->append_off - offset;
465                 goto again;
466         }
467
468         /*
469          * The bigblock might be reserved by another zone.  If it is reserved
470          * by our zone we may have to move next_offset past the append_off.
471          */
472         base_off = (next_offset &
473                     (~HAMMER_LARGEBLOCK_MASK64 & ~HAMMER_OFF_ZONE_MASK)) |
474                     HAMMER_ZONE_RAW_BUFFER;
475         resv = RB_LOOKUP(hammer_res_rb_tree, &hmp->rb_resv_root, base_off);
476         if (resv) {
477                 if (resv->zone != zone) {
478                         hammer_unlock(&hmp->blkmap_lock);
479                         next_offset = (next_offset + HAMMER_LARGEBLOCK_SIZE) &
480                                       ~HAMMER_LARGEBLOCK_MASK64;
481                         goto again;
482                 }
483                 if (offset < resv->append_off) {
484                         hammer_unlock(&hmp->blkmap_lock);
485                         next_offset += resv->append_off - offset;
486                         goto again;
487                 }
488                 ++resv->refs;
489                 resx = NULL;
490         } else {
491                 resx = kmalloc(sizeof(*resv), M_HAMMER,
492                                M_WAITOK | M_ZERO | M_USE_RESERVE);
493                 resx->refs = 1;
494                 resx->zone = zone;
495                 resx->zone_offset = base_off;
496                 resv = RB_INSERT(hammer_res_rb_tree, &hmp->rb_resv_root, resx);
497                 KKASSERT(resv == NULL);
498                 resv = resx;
499                 ++hammer_count_reservations;
500         }
501         resv->append_off = offset + bytes;
502
503         /*
504          * If we are not reserving a whole buffer but are at the start of
505          * a new block, call hammer_bnew() to avoid a disk read.
506          *
507          * If we are reserving a whole buffer (or more), the caller will
508          * probably use a direct read, so do nothing.
509          */
510         if (bytes < HAMMER_BUFSIZE && (next_offset & HAMMER_BUFMASK) == 0) {
511                 hammer_bnew(hmp, next_offset, errorp, &buffer3);
512         }
513
514         /*
515          * Adjust our iterator and alloc_offset.  The layer1 and layer2
516          * space beyond alloc_offset is uninitialized.  alloc_offset must
517          * be big-block aligned.
518          */
519         blockmap->next_offset = next_offset + bytes;
520         hammer_unlock(&hmp->blkmap_lock);
521
522 failed:
523         if (buffer1)
524                 hammer_rel_buffer(buffer1, 0);
525         if (buffer2)
526                 hammer_rel_buffer(buffer2, 0);
527         if (buffer3)
528                 hammer_rel_buffer(buffer3, 0);
529         hammer_rel_volume(root_volume, 0);
530         *zone_offp = next_offset;
531
532         return(resv);
533 }
534
535 /*
536  * A record with a storage reservation calls this function when it is
537  * being freed.  The storage may or may not have actually been allocated.
538  *
539  * This function removes the lock that prevented other entities from
540  * allocating out of the storage or removing the zone assignment.
541  */
542 void
543 hammer_blockmap_reserve_complete(hammer_mount_t hmp, hammer_reserve_t resv)
544 {
545         KKASSERT(resv->refs > 0);
546         if (--resv->refs == 0) {
547                 KKASSERT((resv->flags & HAMMER_RESF_ONDELAY) == 0);
548                 RB_REMOVE(hammer_res_rb_tree, &hmp->rb_resv_root, resv);
549                 kfree(resv, M_HAMMER);
550                 --hammer_count_reservations;
551         }
552 }
553
554 /*
555  * This ensures that no data reallocations will take place at the specified
556  * zone2_offset (pointing to the base of a bigblock) for 2 flush cycles,
557  * preventing deleted data space, which has no UNDO, from being reallocated 
558  * too quickly.
559  */
560 static int
561 hammer_reserve_setdelay(hammer_mount_t hmp, hammer_reserve_t resv,
562                         hammer_off_t zone2_offset)
563 {
564         int error;
565
566         if (resv == NULL) {
567                 resv = kmalloc(sizeof(*resv), M_HAMMER,
568                                M_WAITOK | M_ZERO | M_USE_RESERVE);
569                 resv->refs = 1; /* ref for on-delay list */
570                 resv->zone_offset = zone2_offset;
571                 resv->append_off = HAMMER_LARGEBLOCK_SIZE;
572                 if (RB_INSERT(hammer_res_rb_tree, &hmp->rb_resv_root, resv)) {
573                         error = EAGAIN;
574                         kfree(resv, M_HAMMER);
575                 } else {
576                         error = 0;
577                         ++hammer_count_reservations;
578                 }
579         } else if (resv->flags & HAMMER_RESF_ONDELAY) {
580                 --hmp->rsv_fromdelay;
581                 resv->flags &= ~HAMMER_RESF_ONDELAY;
582                 TAILQ_REMOVE(&hmp->delay_list, resv, delay_entry);
583                 resv->flush_group = hmp->flusher.next + 1;
584                 error = 0;
585         } else {
586                 ++resv->refs;   /* ref for on-delay list */
587                 error = 0;
588         }
589         if (error == 0) {
590                 ++hmp->rsv_fromdelay;
591                 resv->flags |= HAMMER_RESF_ONDELAY;
592                 resv->flush_group = hmp->flusher.next + 1;
593                 TAILQ_INSERT_TAIL(&hmp->delay_list, resv, delay_entry);
594         }
595         return(error);
596 }
597
598 void
599 hammer_reserve_clrdelay(hammer_mount_t hmp, hammer_reserve_t resv)
600 {
601         KKASSERT(resv->flags & HAMMER_RESF_ONDELAY);
602         resv->flags &= ~HAMMER_RESF_ONDELAY;
603         TAILQ_REMOVE(&hmp->delay_list, resv, delay_entry);
604         --hmp->rsv_fromdelay;
605         hammer_blockmap_reserve_complete(hmp, resv);
606 }
607
608 /*
609  * Backend function - free (offset, bytes) in a zone.
610  */
611 void
612 hammer_blockmap_free(hammer_transaction_t trans,
613                      hammer_off_t zone_offset, int bytes)
614 {
615         hammer_mount_t hmp;
616         hammer_volume_t root_volume;
617         hammer_reserve_t resv;
618         hammer_blockmap_t blockmap;
619         hammer_blockmap_t freemap;
620         struct hammer_blockmap_layer1 *layer1;
621         struct hammer_blockmap_layer2 *layer2;
622         hammer_buffer_t buffer1 = NULL;
623         hammer_buffer_t buffer2 = NULL;
624         hammer_off_t layer1_offset;
625         hammer_off_t layer2_offset;
626         hammer_off_t base_off;
627         int error;
628         int zone;
629
630         if (bytes == 0)
631                 return;
632         hmp = trans->hmp;
633
634         /*
635          * Alignment
636          */
637         bytes = (bytes + 15) & ~15;
638         KKASSERT(bytes <= HAMMER_XBUFSIZE);
639         KKASSERT(((zone_offset ^ (zone_offset + (bytes - 1))) & 
640                   ~HAMMER_LARGEBLOCK_MASK64) == 0);
641
642         /*
643          * Basic zone validation & locking
644          */
645         zone = HAMMER_ZONE_DECODE(zone_offset);
646         KKASSERT(zone >= HAMMER_ZONE_BTREE_INDEX && zone < HAMMER_MAX_ZONES);
647         root_volume = trans->rootvol;
648         error = 0;
649
650         blockmap = &hmp->blockmap[zone];
651         freemap = &hmp->blockmap[HAMMER_ZONE_FREEMAP_INDEX];
652
653         /*
654          * Dive layer 1.
655          */
656         layer1_offset = freemap->phys_offset +
657                         HAMMER_BLOCKMAP_LAYER1_OFFSET(zone_offset);
658         layer1 = hammer_bread(hmp, layer1_offset, &error, &buffer1);
659         KKASSERT(error == 0);
660         KKASSERT(layer1->phys_offset &&
661                  layer1->phys_offset != HAMMER_BLOCKMAP_UNAVAIL);
662         if (layer1->layer1_crc != crc32(layer1, HAMMER_LAYER1_CRCSIZE)) {
663                 Debugger("CRC FAILED: LAYER1");
664         }
665
666         /*
667          * Dive layer 2, each entry represents a large-block.
668          */
669         layer2_offset = layer1->phys_offset +
670                         HAMMER_BLOCKMAP_LAYER2_OFFSET(zone_offset);
671         layer2 = hammer_bread(hmp, layer2_offset, &error, &buffer2);
672         KKASSERT(error == 0);
673         if (layer2->entry_crc != crc32(layer2, HAMMER_LAYER2_CRCSIZE)) {
674                 Debugger("CRC FAILED: LAYER2");
675         }
676
677         hammer_lock_ex(&hmp->blkmap_lock);
678
679         hammer_modify_buffer(trans, buffer2, layer2, sizeof(*layer2));
680
681         /*
682          * Freeing previously allocated space
683          */
684         KKASSERT(layer2->zone == zone);
685         layer2->bytes_free += bytes;
686         KKASSERT(layer2->bytes_free <= HAMMER_LARGEBLOCK_SIZE);
687         if (layer2->bytes_free == HAMMER_LARGEBLOCK_SIZE) {
688                 base_off = (zone_offset & (~HAMMER_LARGEBLOCK_MASK64 & ~HAMMER_OFF_ZONE_MASK)) | HAMMER_ZONE_RAW_BUFFER;
689 again:
690                 resv = RB_LOOKUP(hammer_res_rb_tree, &hmp->rb_resv_root,
691                                  base_off);
692                 if (resv) {
693                         /*
694                          * Portions of this block have been reserved, do
695                          * not free it.
696                          *
697                          * Make sure the reservation remains through
698                          * the next flush cycle so potentially undoable
699                          * data is not overwritten.
700                          */
701                         KKASSERT(resv->zone == zone);
702                         hammer_reserve_setdelay(hmp, resv, base_off);
703                 } else if ((blockmap->next_offset ^ zone_offset) &
704                             ~HAMMER_LARGEBLOCK_MASK64) {
705                         /*
706                          * Our iterator is not in the now-free big-block
707                          * and we can release it.
708                          *
709                          * Make sure the reservation remains through
710                          * the next flush cycle so potentially undoable
711                          * data is not overwritten.
712                          */
713                         if (hammer_reserve_setdelay(hmp, resv, base_off))
714                                 goto again;
715                         KKASSERT(layer2->zone == zone);
716                         hammer_del_buffers(hmp,
717                                            zone_offset &
718                                               ~HAMMER_LARGEBLOCK_MASK64,
719                                            base_off,
720                                            HAMMER_LARGEBLOCK_SIZE);
721                         layer2->zone = 0;
722                         layer2->append_off = 0;
723                         hammer_modify_buffer(trans, buffer1,
724                                              layer1, sizeof(*layer1));
725                         ++layer1->blocks_free;
726                         layer1->layer1_crc = crc32(layer1,
727                                                    HAMMER_LAYER1_CRCSIZE);
728                         hammer_modify_buffer_done(buffer1);
729                         hammer_modify_volume_field(trans,
730                                         trans->rootvol,
731                                         vol0_stat_freebigblocks);
732                         ++root_volume->ondisk->vol0_stat_freebigblocks;
733                         hmp->copy_stat_freebigblocks =
734                            root_volume->ondisk->vol0_stat_freebigblocks;
735                         hammer_modify_volume_done(trans->rootvol);
736                 }
737         }
738
739         layer2->entry_crc = crc32(layer2, HAMMER_LAYER2_CRCSIZE);
740         hammer_modify_buffer_done(buffer2);
741         hammer_unlock(&hmp->blkmap_lock);
742
743         if (buffer1)
744                 hammer_rel_buffer(buffer1, 0);
745         if (buffer2)
746                 hammer_rel_buffer(buffer2, 0);
747 }
748
749 /*
750  * Backend function - finalize (offset, bytes) in a zone.
751  *
752  * Allocate space that was previously reserved by the frontend.
753  */
754 void
755 hammer_blockmap_finalize(hammer_transaction_t trans,
756                          hammer_off_t zone_offset, int bytes)
757 {
758         hammer_mount_t hmp;
759         hammer_volume_t root_volume;
760         hammer_blockmap_t blockmap;
761         hammer_blockmap_t freemap;
762         struct hammer_blockmap_layer1 *layer1;
763         struct hammer_blockmap_layer2 *layer2;
764         hammer_buffer_t buffer1 = NULL;
765         hammer_buffer_t buffer2 = NULL;
766         hammer_off_t layer1_offset;
767         hammer_off_t layer2_offset;
768         int error;
769         int zone;
770         int offset;
771
772         if (bytes == 0)
773                 return;
774         hmp = trans->hmp;
775
776         /*
777          * Alignment
778          */
779         bytes = (bytes + 15) & ~15;
780         KKASSERT(bytes <= HAMMER_XBUFSIZE);
781
782         /*
783          * Basic zone validation & locking
784          */
785         zone = HAMMER_ZONE_DECODE(zone_offset);
786         KKASSERT(zone >= HAMMER_ZONE_BTREE_INDEX && zone < HAMMER_MAX_ZONES);
787         root_volume = trans->rootvol;
788         error = 0;
789
790         blockmap = &hmp->blockmap[zone];
791         freemap = &hmp->blockmap[HAMMER_ZONE_FREEMAP_INDEX];
792
793         /*
794          * Dive layer 1.
795          */
796         layer1_offset = freemap->phys_offset +
797                         HAMMER_BLOCKMAP_LAYER1_OFFSET(zone_offset);
798         layer1 = hammer_bread(hmp, layer1_offset, &error, &buffer1);
799         KKASSERT(error == 0);
800         KKASSERT(layer1->phys_offset &&
801                  layer1->phys_offset != HAMMER_BLOCKMAP_UNAVAIL);
802         if (layer1->layer1_crc != crc32(layer1, HAMMER_LAYER1_CRCSIZE)) {
803                 Debugger("CRC FAILED: LAYER1");
804         }
805
806         /*
807          * Dive layer 2, each entry represents a large-block.
808          */
809         layer2_offset = layer1->phys_offset +
810                         HAMMER_BLOCKMAP_LAYER2_OFFSET(zone_offset);
811         layer2 = hammer_bread(hmp, layer2_offset, &error, &buffer2);
812         KKASSERT(error == 0);
813         if (layer2->entry_crc != crc32(layer2, HAMMER_LAYER2_CRCSIZE)) {
814                 Debugger("CRC FAILED: LAYER2");
815         }
816
817         hammer_lock_ex(&hmp->blkmap_lock);
818
819         hammer_modify_buffer(trans, buffer2, layer2, sizeof(*layer2));
820
821         /*
822          * Finalize some or all of the space covered by a current
823          * reservation.  An allocation in the same layer may have
824          * already assigned ownership.
825          */
826         if (layer2->zone == 0) {
827                 hammer_modify_buffer(trans, buffer1,
828                                      layer1, sizeof(*layer1));
829                 --layer1->blocks_free;
830                 layer1->layer1_crc = crc32(layer1,
831                                            HAMMER_LAYER1_CRCSIZE);
832                 hammer_modify_buffer_done(buffer1);
833                 layer2->zone = zone;
834                 KKASSERT(layer2->bytes_free == HAMMER_LARGEBLOCK_SIZE);
835                 KKASSERT(layer2->append_off == 0);
836                 hammer_modify_volume_field(trans,
837                                 trans->rootvol,
838                                 vol0_stat_freebigblocks);
839                 --root_volume->ondisk->vol0_stat_freebigblocks;
840                 hmp->copy_stat_freebigblocks =
841                    root_volume->ondisk->vol0_stat_freebigblocks;
842                 hammer_modify_volume_done(trans->rootvol);
843         }
844         if (layer2->zone != zone)
845                 kprintf("layer2 zone mismatch %d %d\n", layer2->zone, zone);
846         KKASSERT(layer2->zone == zone);
847         layer2->bytes_free -= bytes;
848
849         /*
850          * Finalizations can occur out of order, or combined with allocations.
851          * append_off must be set to the highest allocated offset.
852          */
853         offset = ((int)zone_offset & HAMMER_LARGEBLOCK_MASK) + bytes;
854         if (layer2->append_off < offset)
855                 layer2->append_off = offset;
856
857         layer2->entry_crc = crc32(layer2, HAMMER_LAYER2_CRCSIZE);
858         hammer_modify_buffer_done(buffer2);
859         hammer_unlock(&hmp->blkmap_lock);
860
861         if (buffer1)
862                 hammer_rel_buffer(buffer1, 0);
863         if (buffer2)
864                 hammer_rel_buffer(buffer2, 0);
865 }
866
867 /*
868  * Return the number of free bytes in the big-block containing the
869  * specified blockmap offset.
870  */
871 int
872 hammer_blockmap_getfree(hammer_mount_t hmp, hammer_off_t zone_offset,
873                         int *curp, int *errorp)
874 {
875         hammer_volume_t root_volume;
876         hammer_blockmap_t blockmap;
877         hammer_blockmap_t freemap;
878         struct hammer_blockmap_layer1 *layer1;
879         struct hammer_blockmap_layer2 *layer2;
880         hammer_buffer_t buffer = NULL;
881         hammer_off_t layer1_offset;
882         hammer_off_t layer2_offset;
883         int bytes;
884         int zone;
885
886         zone = HAMMER_ZONE_DECODE(zone_offset);
887         KKASSERT(zone >= HAMMER_ZONE_BTREE_INDEX && zone < HAMMER_MAX_ZONES);
888         root_volume = hammer_get_root_volume(hmp, errorp);
889         if (*errorp) {
890                 *curp = 0;
891                 return(0);
892         }
893         blockmap = &hmp->blockmap[zone];
894         freemap = &hmp->blockmap[HAMMER_ZONE_FREEMAP_INDEX];
895
896         /*
897          * Dive layer 1.
898          */
899         layer1_offset = freemap->phys_offset +
900                         HAMMER_BLOCKMAP_LAYER1_OFFSET(zone_offset);
901         layer1 = hammer_bread(hmp, layer1_offset, errorp, &buffer);
902         KKASSERT(*errorp == 0);
903         KKASSERT(layer1->phys_offset);
904         if (layer1->layer1_crc != crc32(layer1, HAMMER_LAYER1_CRCSIZE)) {
905                 Debugger("CRC FAILED: LAYER1");
906         }
907
908         /*
909          * Dive layer 2, each entry represents a large-block.
910          */
911         layer2_offset = layer1->phys_offset +
912                         HAMMER_BLOCKMAP_LAYER2_OFFSET(zone_offset);
913         layer2 = hammer_bread(hmp, layer2_offset, errorp, &buffer);
914         KKASSERT(*errorp == 0);
915         if (layer2->entry_crc != crc32(layer2, HAMMER_LAYER2_CRCSIZE)) {
916                 Debugger("CRC FAILED: LAYER2");
917         }
918         KKASSERT(layer2->zone == zone);
919
920         bytes = layer2->bytes_free;
921
922         if ((blockmap->next_offset ^ zone_offset) & ~HAMMER_LARGEBLOCK_MASK64)
923                 *curp = 0;
924         else
925                 *curp = 1;
926         if (buffer)
927                 hammer_rel_buffer(buffer, 0);
928         hammer_rel_volume(root_volume, 0);
929         if (hammer_debug_general & 0x0800) {
930                 kprintf("hammer_blockmap_getfree: %016llx -> %d\n",
931                         zone_offset, bytes);
932         }
933         return(bytes);
934 }
935
936
937 /*
938  * Lookup a blockmap offset.
939  */
940 hammer_off_t
941 hammer_blockmap_lookup(hammer_mount_t hmp, hammer_off_t zone_offset,
942                        int *errorp)
943 {
944         hammer_volume_t root_volume;
945         hammer_blockmap_t freemap;
946         struct hammer_blockmap_layer1 *layer1;
947         struct hammer_blockmap_layer2 *layer2;
948         hammer_buffer_t buffer = NULL;
949         hammer_off_t layer1_offset;
950         hammer_off_t layer2_offset;
951         hammer_off_t result_offset;
952         hammer_off_t base_off;
953         hammer_reserve_t resv;
954         int zone;
955
956         /*
957          * Calculate the zone-2 offset.
958          */
959         zone = HAMMER_ZONE_DECODE(zone_offset);
960         KKASSERT(zone >= HAMMER_ZONE_BTREE_INDEX && zone < HAMMER_MAX_ZONES);
961
962         result_offset = (zone_offset & ~HAMMER_OFF_ZONE_MASK) |
963                         HAMMER_ZONE_RAW_BUFFER;
964
965         /*
966          * We can actually stop here, normal blockmaps are now direct-mapped
967          * onto the freemap and so represent zone-2 addresses.
968          */
969         if (hammer_verify_zone == 0) {
970                 *errorp = 0;
971                 return(result_offset);
972         }
973
974         /*
975          * Validate the allocation zone
976          */
977         root_volume = hammer_get_root_volume(hmp, errorp);
978         if (*errorp)
979                 return(0);
980         freemap = &hmp->blockmap[HAMMER_ZONE_FREEMAP_INDEX];
981         KKASSERT(freemap->phys_offset != 0);
982
983         /*
984          * Dive layer 1.
985          */
986         layer1_offset = freemap->phys_offset +
987                         HAMMER_BLOCKMAP_LAYER1_OFFSET(zone_offset);
988         layer1 = hammer_bread(hmp, layer1_offset, errorp, &buffer);
989         KKASSERT(*errorp == 0);
990         KKASSERT(layer1->phys_offset != HAMMER_BLOCKMAP_UNAVAIL);
991         if (layer1->layer1_crc != crc32(layer1, HAMMER_LAYER1_CRCSIZE)) {
992                 Debugger("CRC FAILED: LAYER1");
993         }
994
995         /*
996          * Dive layer 2, each entry represents a large-block.
997          */
998         layer2_offset = layer1->phys_offset +
999                         HAMMER_BLOCKMAP_LAYER2_OFFSET(zone_offset);
1000         layer2 = hammer_bread(hmp, layer2_offset, errorp, &buffer);
1001
1002         KKASSERT(*errorp == 0);
1003         if (layer2->zone == 0) {
1004                 base_off = (zone_offset & (~HAMMER_LARGEBLOCK_MASK64 & ~HAMMER_OFF_ZONE_MASK)) | HAMMER_ZONE_RAW_BUFFER;
1005                 resv = RB_LOOKUP(hammer_res_rb_tree, &hmp->rb_resv_root,
1006                                  base_off);
1007                 KKASSERT(resv && resv->zone == zone);
1008
1009         } else if (layer2->zone != zone) {
1010                 panic("hammer_blockmap_lookup: bad zone %d/%d\n",
1011                         layer2->zone, zone);
1012         }
1013         if (layer2->entry_crc != crc32(layer2, HAMMER_LAYER2_CRCSIZE)) {
1014                 Debugger("CRC FAILED: LAYER2");
1015         }
1016
1017         if (buffer)
1018                 hammer_rel_buffer(buffer, 0);
1019         hammer_rel_volume(root_volume, 0);
1020         if (hammer_debug_general & 0x0800) {
1021                 kprintf("hammer_blockmap_lookup: %016llx -> %016llx\n",
1022                         zone_offset, result_offset);
1023         }
1024         return(result_offset);
1025 }
1026
1027
1028 /*
1029  * Check space availability
1030  */
1031 int
1032 hammer_checkspace(hammer_mount_t hmp, int slop)
1033 {
1034         const int in_size = sizeof(struct hammer_inode_data) +
1035                             sizeof(union hammer_btree_elm);
1036         const int rec_size = (sizeof(union hammer_btree_elm) * 2);
1037         int64_t usedbytes;
1038
1039         /*
1040          * Hopefully a quick and fast check.
1041          */
1042         if (hmp->copy_stat_freebigblocks * HAMMER_LARGEBLOCK_SIZE >=
1043             (int64_t)hidirtybufspace * 4 + 10 * HAMMER_LARGEBLOCK_SIZE) {
1044                 hammer_count_extra_space_used = -1;
1045                 return(0);
1046         }
1047
1048         /*
1049          * Do a more involved check
1050          */
1051         usedbytes = hmp->rsv_inodes * in_size +
1052                     hmp->rsv_recs * rec_size +
1053                     hmp->rsv_databytes +
1054                     hmp->rsv_fromdelay * HAMMER_LARGEBLOCK_SIZE +
1055                     hidirtybufspace +
1056                     slop * HAMMER_LARGEBLOCK_SIZE;
1057
1058         hammer_count_extra_space_used = usedbytes;
1059
1060         if (hmp->copy_stat_freebigblocks >= usedbytes / HAMMER_LARGEBLOCK_SIZE)
1061                 return(0);
1062         return (ENOSPC);
1063 }
1064