Root/drivers/md/persistent-data/dm-space-map-metadata.c

1/*
2 * Copyright (C) 2011 Red Hat, Inc.
3 *
4 * This file is released under the GPL.
5 */
6
7#include "dm-space-map.h"
8#include "dm-space-map-common.h"
9#include "dm-space-map-metadata.h"
10
11#include <linux/list.h>
12#include <linux/slab.h>
13#include <linux/device-mapper.h>
14
15#define DM_MSG_PREFIX "space map metadata"
16
17/*----------------------------------------------------------------*/
18
19/*
20 * Space map interface.
21 *
22 * The low level disk format is written using the standard btree and
23 * transaction manager. This means that performing disk operations may
24 * cause us to recurse into the space map in order to allocate new blocks.
25 * For this reason we have a pool of pre-allocated blocks large enough to
26 * service any metadata_ll_disk operation.
27 */
28
29/*
30 * FIXME: we should calculate this based on the size of the device.
31 * Only the metadata space map needs this functionality.
32 */
33#define MAX_RECURSIVE_ALLOCATIONS 1024
34
35enum block_op_type {
36    BOP_INC,
37    BOP_DEC
38};
39
40struct block_op {
41    enum block_op_type type;
42    dm_block_t block;
43};
44
45struct sm_metadata {
46    struct dm_space_map sm;
47
48    struct ll_disk ll;
49    struct ll_disk old_ll;
50
51    dm_block_t begin;
52
53    unsigned recursion_count;
54    unsigned allocated_this_transaction;
55    unsigned nr_uncommitted;
56    struct block_op uncommitted[MAX_RECURSIVE_ALLOCATIONS];
57};
58
59static int add_bop(struct sm_metadata *smm, enum block_op_type type, dm_block_t b)
60{
61    struct block_op *op;
62
63    if (smm->nr_uncommitted == MAX_RECURSIVE_ALLOCATIONS) {
64        DMERR("too many recursive allocations");
65        return -ENOMEM;
66    }
67
68    op = smm->uncommitted + smm->nr_uncommitted++;
69    op->type = type;
70    op->block = b;
71
72    return 0;
73}
74
75static int commit_bop(struct sm_metadata *smm, struct block_op *op)
76{
77    int r = 0;
78    enum allocation_event ev;
79
80    switch (op->type) {
81    case BOP_INC:
82        r = sm_ll_inc(&smm->ll, op->block, &ev);
83        break;
84
85    case BOP_DEC:
86        r = sm_ll_dec(&smm->ll, op->block, &ev);
87        break;
88    }
89
90    return r;
91}
92
93static void in(struct sm_metadata *smm)
94{
95    smm->recursion_count++;
96}
97
98static int out(struct sm_metadata *smm)
99{
100    int r = 0;
101
102    /*
103     * If we're not recursing then very bad things are happening.
104     */
105    if (!smm->recursion_count) {
106        DMERR("lost track of recursion depth");
107        return -ENOMEM;
108    }
109
110    if (smm->recursion_count == 1 && smm->nr_uncommitted) {
111        while (smm->nr_uncommitted && !r) {
112            smm->nr_uncommitted--;
113            r = commit_bop(smm, smm->uncommitted +
114                       smm->nr_uncommitted);
115            if (r)
116                break;
117        }
118    }
119
120    smm->recursion_count--;
121
122    return r;
123}
124
125/*
126 * When using the out() function above, we often want to combine an error
127 * code for the operation run in the recursive context with that from
128 * out().
129 */
130static int combine_errors(int r1, int r2)
131{
132    return r1 ? r1 : r2;
133}
134
135static int recursing(struct sm_metadata *smm)
136{
137    return smm->recursion_count;
138}
139
140static void sm_metadata_destroy(struct dm_space_map *sm)
141{
142    struct sm_metadata *smm = container_of(sm, struct sm_metadata, sm);
143
144    kfree(smm);
145}
146
147static int sm_metadata_extend(struct dm_space_map *sm, dm_block_t extra_blocks)
148{
149    DMERR("doesn't support extend");
150    return -EINVAL;
151}
152
153static int sm_metadata_get_nr_blocks(struct dm_space_map *sm, dm_block_t *count)
154{
155    struct sm_metadata *smm = container_of(sm, struct sm_metadata, sm);
156
157    *count = smm->ll.nr_blocks;
158
159    return 0;
160}
161
162static int sm_metadata_get_nr_free(struct dm_space_map *sm, dm_block_t *count)
163{
164    struct sm_metadata *smm = container_of(sm, struct sm_metadata, sm);
165
166    *count = smm->old_ll.nr_blocks - smm->old_ll.nr_allocated -
167         smm->allocated_this_transaction;
168
169    return 0;
170}
171
172static int sm_metadata_get_count(struct dm_space_map *sm, dm_block_t b,
173                 uint32_t *result)
174{
175    int r, i;
176    struct sm_metadata *smm = container_of(sm, struct sm_metadata, sm);
177    unsigned adjustment = 0;
178
179    /*
180     * We may have some uncommitted adjustments to add. This list
181     * should always be really short.
182     */
183    for (i = 0; i < smm->nr_uncommitted; i++) {
184        struct block_op *op = smm->uncommitted + i;
185
186        if (op->block != b)
187            continue;
188
189        switch (op->type) {
190        case BOP_INC:
191            adjustment++;
192            break;
193
194        case BOP_DEC:
195            adjustment--;
196            break;
197        }
198    }
199
200    r = sm_ll_lookup(&smm->ll, b, result);
201    if (r)
202        return r;
203
204    *result += adjustment;
205
206    return 0;
207}
208
209static int sm_metadata_count_is_more_than_one(struct dm_space_map *sm,
210                          dm_block_t b, int *result)
211{
212    int r, i, adjustment = 0;
213    struct sm_metadata *smm = container_of(sm, struct sm_metadata, sm);
214    uint32_t rc;
215
216    /*
217     * We may have some uncommitted adjustments to add. This list
218     * should always be really short.
219     */
220    for (i = 0; i < smm->nr_uncommitted; i++) {
221        struct block_op *op = smm->uncommitted + i;
222
223        if (op->block != b)
224            continue;
225
226        switch (op->type) {
227        case BOP_INC:
228            adjustment++;
229            break;
230
231        case BOP_DEC:
232            adjustment--;
233            break;
234        }
235    }
236
237    if (adjustment > 1) {
238        *result = 1;
239        return 0;
240    }
241
242    r = sm_ll_lookup_bitmap(&smm->ll, b, &rc);
243    if (r)
244        return r;
245
246    if (rc == 3)
247        /*
248         * We err on the side of caution, and always return true.
249         */
250        *result = 1;
251    else
252        *result = rc + adjustment > 1;
253
254    return 0;
255}
256
257static int sm_metadata_set_count(struct dm_space_map *sm, dm_block_t b,
258                 uint32_t count)
259{
260    int r, r2;
261    enum allocation_event ev;
262    struct sm_metadata *smm = container_of(sm, struct sm_metadata, sm);
263
264    if (smm->recursion_count) {
265        DMERR("cannot recurse set_count()");
266        return -EINVAL;
267    }
268
269    in(smm);
270    r = sm_ll_insert(&smm->ll, b, count, &ev);
271    r2 = out(smm);
272
273    return combine_errors(r, r2);
274}
275
276static int sm_metadata_inc_block(struct dm_space_map *sm, dm_block_t b)
277{
278    int r, r2 = 0;
279    enum allocation_event ev;
280    struct sm_metadata *smm = container_of(sm, struct sm_metadata, sm);
281
282    if (recursing(smm))
283        r = add_bop(smm, BOP_INC, b);
284    else {
285        in(smm);
286        r = sm_ll_inc(&smm->ll, b, &ev);
287        r2 = out(smm);
288    }
289
290    return combine_errors(r, r2);
291}
292
293static int sm_metadata_dec_block(struct dm_space_map *sm, dm_block_t b)
294{
295    int r, r2 = 0;
296    enum allocation_event ev;
297    struct sm_metadata *smm = container_of(sm, struct sm_metadata, sm);
298
299    if (recursing(smm))
300        r = add_bop(smm, BOP_DEC, b);
301    else {
302        in(smm);
303        r = sm_ll_dec(&smm->ll, b, &ev);
304        r2 = out(smm);
305    }
306
307    return combine_errors(r, r2);
308}
309
310static int sm_metadata_new_block_(struct dm_space_map *sm, dm_block_t *b)
311{
312    int r, r2 = 0;
313    enum allocation_event ev;
314    struct sm_metadata *smm = container_of(sm, struct sm_metadata, sm);
315
316    r = sm_ll_find_free_block(&smm->old_ll, smm->begin, smm->old_ll.nr_blocks, b);
317    if (r)
318        return r;
319
320    smm->begin = *b + 1;
321
322    if (recursing(smm))
323        r = add_bop(smm, BOP_INC, *b);
324    else {
325        in(smm);
326        r = sm_ll_inc(&smm->ll, *b, &ev);
327        r2 = out(smm);
328    }
329
330    if (!r)
331        smm->allocated_this_transaction++;
332
333    return combine_errors(r, r2);
334}
335
336static int sm_metadata_new_block(struct dm_space_map *sm, dm_block_t *b)
337{
338    int r = sm_metadata_new_block_(sm, b);
339    if (r)
340        DMERR("out of metadata space");
341    return r;
342}
343
344static int sm_metadata_commit(struct dm_space_map *sm)
345{
346    int r;
347    struct sm_metadata *smm = container_of(sm, struct sm_metadata, sm);
348
349    r = sm_ll_commit(&smm->ll);
350    if (r)
351        return r;
352
353    memcpy(&smm->old_ll, &smm->ll, sizeof(smm->old_ll));
354    smm->begin = 0;
355    smm->allocated_this_transaction = 0;
356
357    return 0;
358}
359
360static int sm_metadata_root_size(struct dm_space_map *sm, size_t *result)
361{
362    *result = sizeof(struct disk_sm_root);
363
364    return 0;
365}
366
367static int sm_metadata_copy_root(struct dm_space_map *sm, void *where_le, size_t max)
368{
369    struct sm_metadata *smm = container_of(sm, struct sm_metadata, sm);
370    struct disk_sm_root root_le;
371
372    root_le.nr_blocks = cpu_to_le64(smm->ll.nr_blocks);
373    root_le.nr_allocated = cpu_to_le64(smm->ll.nr_allocated);
374    root_le.bitmap_root = cpu_to_le64(smm->ll.bitmap_root);
375    root_le.ref_count_root = cpu_to_le64(smm->ll.ref_count_root);
376
377    if (max < sizeof(root_le))
378        return -ENOSPC;
379
380    memcpy(where_le, &root_le, sizeof(root_le));
381
382    return 0;
383}
384
385static struct dm_space_map ops = {
386    .destroy = sm_metadata_destroy,
387    .extend = sm_metadata_extend,
388    .get_nr_blocks = sm_metadata_get_nr_blocks,
389    .get_nr_free = sm_metadata_get_nr_free,
390    .get_count = sm_metadata_get_count,
391    .count_is_more_than_one = sm_metadata_count_is_more_than_one,
392    .set_count = sm_metadata_set_count,
393    .inc_block = sm_metadata_inc_block,
394    .dec_block = sm_metadata_dec_block,
395    .new_block = sm_metadata_new_block,
396    .commit = sm_metadata_commit,
397    .root_size = sm_metadata_root_size,
398    .copy_root = sm_metadata_copy_root
399};
400
401/*----------------------------------------------------------------*/
402
403/*
404 * When a new space map is created that manages its own space. We use
405 * this tiny bootstrap allocator.
406 */
407static void sm_bootstrap_destroy(struct dm_space_map *sm)
408{
409}
410
411static int sm_bootstrap_extend(struct dm_space_map *sm, dm_block_t extra_blocks)
412{
413    DMERR("boostrap doesn't support extend");
414
415    return -EINVAL;
416}
417
418static int sm_bootstrap_get_nr_blocks(struct dm_space_map *sm, dm_block_t *count)
419{
420    struct sm_metadata *smm = container_of(sm, struct sm_metadata, sm);
421
422    return smm->ll.nr_blocks;
423}
424
425static int sm_bootstrap_get_nr_free(struct dm_space_map *sm, dm_block_t *count)
426{
427    struct sm_metadata *smm = container_of(sm, struct sm_metadata, sm);
428
429    *count = smm->ll.nr_blocks - smm->begin;
430
431    return 0;
432}
433
434static int sm_bootstrap_get_count(struct dm_space_map *sm, dm_block_t b,
435                  uint32_t *result)
436{
437    struct sm_metadata *smm = container_of(sm, struct sm_metadata, sm);
438
439    return b < smm->begin ? 1 : 0;
440}
441
442static int sm_bootstrap_count_is_more_than_one(struct dm_space_map *sm,
443                           dm_block_t b, int *result)
444{
445    *result = 0;
446
447    return 0;
448}
449
450static int sm_bootstrap_set_count(struct dm_space_map *sm, dm_block_t b,
451                  uint32_t count)
452{
453    DMERR("boostrap doesn't support set_count");
454
455    return -EINVAL;
456}
457
458static int sm_bootstrap_new_block(struct dm_space_map *sm, dm_block_t *b)
459{
460    struct sm_metadata *smm = container_of(sm, struct sm_metadata, sm);
461
462    /*
463     * We know the entire device is unused.
464     */
465    if (smm->begin == smm->ll.nr_blocks)
466        return -ENOSPC;
467
468    *b = smm->begin++;
469
470    return 0;
471}
472
473static int sm_bootstrap_inc_block(struct dm_space_map *sm, dm_block_t b)
474{
475    struct sm_metadata *smm = container_of(sm, struct sm_metadata, sm);
476
477    return add_bop(smm, BOP_INC, b);
478}
479
480static int sm_bootstrap_dec_block(struct dm_space_map *sm, dm_block_t b)
481{
482    struct sm_metadata *smm = container_of(sm, struct sm_metadata, sm);
483
484    return add_bop(smm, BOP_DEC, b);
485}
486
487static int sm_bootstrap_commit(struct dm_space_map *sm)
488{
489    return 0;
490}
491
492static int sm_bootstrap_root_size(struct dm_space_map *sm, size_t *result)
493{
494    DMERR("boostrap doesn't support root_size");
495
496    return -EINVAL;
497}
498
499static int sm_bootstrap_copy_root(struct dm_space_map *sm, void *where,
500                  size_t max)
501{
502    DMERR("boostrap doesn't support copy_root");
503
504    return -EINVAL;
505}
506
507static struct dm_space_map bootstrap_ops = {
508    .destroy = sm_bootstrap_destroy,
509    .extend = sm_bootstrap_extend,
510    .get_nr_blocks = sm_bootstrap_get_nr_blocks,
511    .get_nr_free = sm_bootstrap_get_nr_free,
512    .get_count = sm_bootstrap_get_count,
513    .count_is_more_than_one = sm_bootstrap_count_is_more_than_one,
514    .set_count = sm_bootstrap_set_count,
515    .inc_block = sm_bootstrap_inc_block,
516    .dec_block = sm_bootstrap_dec_block,
517    .new_block = sm_bootstrap_new_block,
518    .commit = sm_bootstrap_commit,
519    .root_size = sm_bootstrap_root_size,
520    .copy_root = sm_bootstrap_copy_root
521};
522
523/*----------------------------------------------------------------*/
524
525struct dm_space_map *dm_sm_metadata_init(void)
526{
527    struct sm_metadata *smm;
528
529    smm = kmalloc(sizeof(*smm), GFP_KERNEL);
530    if (!smm)
531        return ERR_PTR(-ENOMEM);
532
533    memcpy(&smm->sm, &ops, sizeof(smm->sm));
534
535    return &smm->sm;
536}
537
538int dm_sm_metadata_create(struct dm_space_map *sm,
539              struct dm_transaction_manager *tm,
540              dm_block_t nr_blocks,
541              dm_block_t superblock)
542{
543    int r;
544    dm_block_t i;
545    enum allocation_event ev;
546    struct sm_metadata *smm = container_of(sm, struct sm_metadata, sm);
547
548    smm->begin = superblock + 1;
549    smm->recursion_count = 0;
550    smm->allocated_this_transaction = 0;
551    smm->nr_uncommitted = 0;
552
553    memcpy(&smm->sm, &bootstrap_ops, sizeof(smm->sm));
554
555    r = sm_ll_new_metadata(&smm->ll, tm);
556    if (r)
557        return r;
558
559    r = sm_ll_extend(&smm->ll, nr_blocks);
560    if (r)
561        return r;
562
563    memcpy(&smm->sm, &ops, sizeof(smm->sm));
564
565    /*
566     * Now we need to update the newly created data structures with the
567     * allocated blocks that they were built from.
568     */
569    for (i = superblock; !r && i < smm->begin; i++)
570        r = sm_ll_inc(&smm->ll, i, &ev);
571
572    if (r)
573        return r;
574
575    return sm_metadata_commit(sm);
576}
577
578int dm_sm_metadata_open(struct dm_space_map *sm,
579            struct dm_transaction_manager *tm,
580            void *root_le, size_t len)
581{
582    int r;
583    struct sm_metadata *smm = container_of(sm, struct sm_metadata, sm);
584
585    r = sm_ll_open_metadata(&smm->ll, tm, root_le, len);
586    if (r)
587        return r;
588
589    smm->begin = 0;
590    smm->recursion_count = 0;
591    smm->allocated_this_transaction = 0;
592    smm->nr_uncommitted = 0;
593
594    memcpy(&smm->old_ll, &smm->ll, sizeof(smm->old_ll));
595    return 0;
596}
597

Archive Download this file



interactive