2 * Copyright (C) 2001 Sistina Software (UK) Limited.
3 * Copyright (C) 2004 Red Hat, Inc. All rights reserved.
5 * This file is released under the GPL.
10 #include <linux/module.h>
11 #include <linux/vmalloc.h>
12 #include <linux/blkdev.h>
13 #include <linux/namei.h>
14 #include <linux/ctype.h>
15 #include <linux/slab.h>
16 #include <linux/interrupt.h>
17 #include <linux/mutex.h>
18 #include <asm/atomic.h>
20 #define DM_MSG_PREFIX "table"
23 #define NODE_SIZE L1_CACHE_BYTES
24 #define KEYS_PER_NODE (NODE_SIZE / sizeof(sector_t))
25 #define CHILDREN_PER_NODE (KEYS_PER_NODE + 1)
28 struct mapped_device
*md
;
33 unsigned int counts
[MAX_DEPTH
]; /* in nodes */
34 sector_t
*index
[MAX_DEPTH
];
36 unsigned int num_targets
;
37 unsigned int num_allocated
;
39 struct dm_target
*targets
;
42 * Indicates the rw permissions for the new logical
43 * device. This should be a combination of FMODE_READ
48 /* a list of devices used by this table */
49 struct list_head devices
;
52 * These are optimistic limits taken from all the
53 * targets, some targets will need smaller limits.
55 struct io_restrictions limits
;
57 /* events get handed up using this callback */
58 void (*event_fn
)(void *);
63 * Similar to ceiling(log_size(n))
65 static unsigned int int_log(unsigned int n
, unsigned int base
)
70 n
= dm_div_up(n
, base
);
78 * Returns the minimum that is _not_ zero, unless both are zero.
80 #define min_not_zero(l, r) (l == 0) ? r : ((r == 0) ? l : min(l, r))
83 * Combine two io_restrictions, always taking the lower value.
85 static void combine_restrictions_low(struct io_restrictions
*lhs
,
86 struct io_restrictions
*rhs
)
89 min_not_zero(lhs
->max_sectors
, rhs
->max_sectors
);
91 lhs
->max_phys_segments
=
92 min_not_zero(lhs
->max_phys_segments
, rhs
->max_phys_segments
);
94 lhs
->max_hw_segments
=
95 min_not_zero(lhs
->max_hw_segments
, rhs
->max_hw_segments
);
97 lhs
->hardsect_size
= max(lhs
->hardsect_size
, rhs
->hardsect_size
);
99 lhs
->max_segment_size
=
100 min_not_zero(lhs
->max_segment_size
, rhs
->max_segment_size
);
102 lhs
->max_hw_sectors
=
103 min_not_zero(lhs
->max_hw_sectors
, rhs
->max_hw_sectors
);
105 lhs
->seg_boundary_mask
=
106 min_not_zero(lhs
->seg_boundary_mask
, rhs
->seg_boundary_mask
);
108 lhs
->bounce_pfn
= min_not_zero(lhs
->bounce_pfn
, rhs
->bounce_pfn
);
110 lhs
->no_cluster
|= rhs
->no_cluster
;
114 * Calculate the index of the child node of the n'th node k'th key.
116 static inline unsigned int get_child(unsigned int n
, unsigned int k
)
118 return (n
* CHILDREN_PER_NODE
) + k
;
122 * Return the n'th node of level l from table t.
124 static inline sector_t
*get_node(struct dm_table
*t
,
125 unsigned int l
, unsigned int n
)
127 return t
->index
[l
] + (n
* KEYS_PER_NODE
);
131 * Return the highest key that you could lookup from the n'th
132 * node on level l of the btree.
134 static sector_t
high(struct dm_table
*t
, unsigned int l
, unsigned int n
)
136 for (; l
< t
->depth
- 1; l
++)
137 n
= get_child(n
, CHILDREN_PER_NODE
- 1);
139 if (n
>= t
->counts
[l
])
140 return (sector_t
) - 1;
142 return get_node(t
, l
, n
)[KEYS_PER_NODE
- 1];
146 * Fills in a level of the btree based on the highs of the level
149 static int setup_btree_index(unsigned int l
, struct dm_table
*t
)
154 for (n
= 0U; n
< t
->counts
[l
]; n
++) {
155 node
= get_node(t
, l
, n
);
157 for (k
= 0U; k
< KEYS_PER_NODE
; k
++)
158 node
[k
] = high(t
, l
+ 1, get_child(n
, k
));
164 void *dm_vcalloc(unsigned long nmemb
, unsigned long elem_size
)
170 * Check that we're not going to overflow.
172 if (nmemb
> (ULONG_MAX
/ elem_size
))
175 size
= nmemb
* elem_size
;
176 addr
= vmalloc(size
);
178 memset(addr
, 0, size
);
184 * highs, and targets are managed as dynamic arrays during a
187 static int alloc_targets(struct dm_table
*t
, unsigned int num
)
190 struct dm_target
*n_targets
;
191 int n
= t
->num_targets
;
194 * Allocate both the target array and offset array at once.
195 * Append an empty entry to catch sectors beyond the end of
198 n_highs
= (sector_t
*) dm_vcalloc(num
+ 1, sizeof(struct dm_target
) +
203 n_targets
= (struct dm_target
*) (n_highs
+ num
);
206 memcpy(n_highs
, t
->highs
, sizeof(*n_highs
) * n
);
207 memcpy(n_targets
, t
->targets
, sizeof(*n_targets
) * n
);
210 memset(n_highs
+ n
, -1, sizeof(*n_highs
) * (num
- n
));
213 t
->num_allocated
= num
;
215 t
->targets
= n_targets
;
220 int dm_table_create(struct dm_table
**result
, int mode
,
221 unsigned num_targets
, struct mapped_device
*md
)
223 struct dm_table
*t
= kzalloc(sizeof(*t
), GFP_KERNEL
);
228 INIT_LIST_HEAD(&t
->devices
);
229 atomic_set(&t
->holders
, 1);
232 num_targets
= KEYS_PER_NODE
;
234 num_targets
= dm_round_up(num_targets
, KEYS_PER_NODE
);
236 if (alloc_targets(t
, num_targets
)) {
248 int dm_create_error_table(struct dm_table
**result
, struct mapped_device
*md
)
251 sector_t dev_size
= 1;
255 * Find current size of device.
256 * Default to 1 sector if inactive.
258 t
= dm_get_table(md
);
260 dev_size
= dm_table_get_size(t
);
264 r
= dm_table_create(&t
, FMODE_READ
, 1, md
);
268 r
= dm_table_add_target(t
, "error", 0, dev_size
, NULL
);
272 r
= dm_table_complete(t
);
284 EXPORT_SYMBOL_GPL(dm_create_error_table
);
286 static void free_devices(struct list_head
*devices
)
288 struct list_head
*tmp
, *next
;
290 for (tmp
= devices
->next
; tmp
!= devices
; tmp
= next
) {
291 struct dm_dev
*dd
= list_entry(tmp
, struct dm_dev
, list
);
297 static void table_destroy(struct dm_table
*t
)
301 /* free the indexes (see dm_table_complete) */
303 vfree(t
->index
[t
->depth
- 2]);
305 /* free the targets */
306 for (i
= 0; i
< t
->num_targets
; i
++) {
307 struct dm_target
*tgt
= t
->targets
+ i
;
312 dm_put_target_type(tgt
->type
);
317 /* free the device list */
318 if (t
->devices
.next
!= &t
->devices
) {
319 DMWARN("devices still present during destroy: "
320 "dm_table_remove_device calls missing");
322 free_devices(&t
->devices
);
328 void dm_table_get(struct dm_table
*t
)
330 atomic_inc(&t
->holders
);
333 void dm_table_put(struct dm_table
*t
)
338 if (atomic_dec_and_test(&t
->holders
))
343 * Checks to see if we need to extend highs or targets.
345 static inline int check_space(struct dm_table
*t
)
347 if (t
->num_targets
>= t
->num_allocated
)
348 return alloc_targets(t
, t
->num_allocated
* 2);
354 * Convert a device path to a dev_t.
356 static int lookup_device(const char *path
, dev_t
*dev
)
362 if ((r
= path_lookup(path
, LOOKUP_FOLLOW
, &nd
)))
365 inode
= nd
.dentry
->d_inode
;
371 if (!S_ISBLK(inode
->i_mode
)) {
376 *dev
= inode
->i_rdev
;
384 * See if we've already got a device in the list.
386 static struct dm_dev
*find_device(struct list_head
*l
, dev_t dev
)
390 list_for_each_entry (dd
, l
, list
)
391 if (dd
->bdev
->bd_dev
== dev
)
398 * Open a device so we can use it as a map destination.
400 static int open_dev(struct dm_dev
*d
, dev_t dev
, struct mapped_device
*md
)
402 static char *_claim_ptr
= "I belong to device-mapper";
403 struct block_device
*bdev
;
409 bdev
= open_by_devnum(dev
, d
->mode
);
411 return PTR_ERR(bdev
);
412 r
= bd_claim_by_disk(bdev
, _claim_ptr
, dm_disk(md
));
421 * Close a device that we've been using.
423 static void close_dev(struct dm_dev
*d
, struct mapped_device
*md
)
428 bd_release_from_disk(d
->bdev
, dm_disk(md
));
434 * If possible, this checks an area of a destination device is valid.
436 static int check_device_area(struct dm_dev
*dd
, sector_t start
, sector_t len
)
438 sector_t dev_size
= dd
->bdev
->bd_inode
->i_size
>> SECTOR_SHIFT
;
443 return ((start
< dev_size
) && (len
<= (dev_size
- start
)));
447 * This upgrades the mode on an already open dm_dev. Being
448 * careful to leave things as they were if we fail to reopen the
451 static int upgrade_mode(struct dm_dev
*dd
, int new_mode
, struct mapped_device
*md
)
454 struct dm_dev dd_copy
;
455 dev_t dev
= dd
->bdev
->bd_dev
;
459 dd
->mode
|= new_mode
;
461 r
= open_dev(dd
, dev
, md
);
463 close_dev(&dd_copy
, md
);
471 * Add a device to the list, or just increment the usage count if
472 * it's already present.
474 static int __table_get_device(struct dm_table
*t
, struct dm_target
*ti
,
475 const char *path
, sector_t start
, sector_t len
,
476 int mode
, struct dm_dev
**result
)
481 unsigned int major
, minor
;
485 if (sscanf(path
, "%u:%u", &major
, &minor
) == 2) {
486 /* Extract the major/minor numbers */
487 dev
= MKDEV(major
, minor
);
488 if (MAJOR(dev
) != major
|| MINOR(dev
) != minor
)
491 /* convert the path to a device */
492 if ((r
= lookup_device(path
, &dev
)))
496 dd
= find_device(&t
->devices
, dev
);
498 dd
= kmalloc(sizeof(*dd
), GFP_KERNEL
);
505 if ((r
= open_dev(dd
, dev
, t
->md
))) {
510 format_dev_t(dd
->name
, dev
);
512 atomic_set(&dd
->count
, 0);
513 list_add(&dd
->list
, &t
->devices
);
515 } else if (dd
->mode
!= (mode
| dd
->mode
)) {
516 r
= upgrade_mode(dd
, mode
, t
->md
);
520 atomic_inc(&dd
->count
);
522 if (!check_device_area(dd
, start
, len
)) {
523 DMWARN("device %s too small for target", path
);
524 dm_put_device(ti
, dd
);
533 void dm_set_device_limits(struct dm_target
*ti
, struct block_device
*bdev
)
535 struct request_queue
*q
= bdev_get_queue(bdev
);
536 struct io_restrictions
*rs
= &ti
->limits
;
539 * Combine the device limits low.
541 * FIXME: if we move an io_restriction struct
542 * into q this would just be a call to
543 * combine_restrictions_low()
546 min_not_zero(rs
->max_sectors
, q
->max_sectors
);
548 /* FIXME: Device-Mapper on top of RAID-0 breaks because DM
549 * currently doesn't honor MD's merge_bvec_fn routine.
550 * In this case, we'll force DM to use PAGE_SIZE or
551 * smaller I/O, just to be safe. A better fix is in the
552 * works, but add this for the time being so it will at
553 * least operate correctly.
555 if (q
->merge_bvec_fn
)
557 min_not_zero(rs
->max_sectors
,
558 (unsigned int) (PAGE_SIZE
>> 9));
560 rs
->max_phys_segments
=
561 min_not_zero(rs
->max_phys_segments
,
562 q
->max_phys_segments
);
564 rs
->max_hw_segments
=
565 min_not_zero(rs
->max_hw_segments
, q
->max_hw_segments
);
567 rs
->hardsect_size
= max(rs
->hardsect_size
, q
->hardsect_size
);
569 rs
->max_segment_size
=
570 min_not_zero(rs
->max_segment_size
, q
->max_segment_size
);
573 min_not_zero(rs
->max_hw_sectors
, q
->max_hw_sectors
);
575 rs
->seg_boundary_mask
=
576 min_not_zero(rs
->seg_boundary_mask
,
577 q
->seg_boundary_mask
);
579 rs
->bounce_pfn
= min_not_zero(rs
->bounce_pfn
, q
->bounce_pfn
);
581 rs
->no_cluster
|= !test_bit(QUEUE_FLAG_CLUSTER
, &q
->queue_flags
);
583 EXPORT_SYMBOL_GPL(dm_set_device_limits
);
585 int dm_get_device(struct dm_target
*ti
, const char *path
, sector_t start
,
586 sector_t len
, int mode
, struct dm_dev
**result
)
588 int r
= __table_get_device(ti
->table
, ti
, path
,
589 start
, len
, mode
, result
);
592 dm_set_device_limits(ti
, (*result
)->bdev
);
598 * Decrement a devices use count and remove it if necessary.
600 void dm_put_device(struct dm_target
*ti
, struct dm_dev
*dd
)
602 if (atomic_dec_and_test(&dd
->count
)) {
603 close_dev(dd
, ti
->table
->md
);
610 * Checks to see if the target joins onto the end of the table.
612 static int adjoin(struct dm_table
*table
, struct dm_target
*ti
)
614 struct dm_target
*prev
;
616 if (!table
->num_targets
)
619 prev
= &table
->targets
[table
->num_targets
- 1];
620 return (ti
->begin
== (prev
->begin
+ prev
->len
));
624 * Used to dynamically allocate the arg array.
626 static char **realloc_argv(unsigned *array_size
, char **old_argv
)
631 new_size
= *array_size
? *array_size
* 2 : 64;
632 argv
= kmalloc(new_size
* sizeof(*argv
), GFP_KERNEL
);
634 memcpy(argv
, old_argv
, *array_size
* sizeof(*argv
));
635 *array_size
= new_size
;
643 * Destructively splits up the argument list to pass to ctr.
645 int dm_split_args(int *argc
, char ***argvp
, char *input
)
647 char *start
, *end
= input
, *out
, **argv
= NULL
;
648 unsigned array_size
= 0;
657 argv
= realloc_argv(&array_size
, argv
);
664 /* Skip whitespace */
665 while (*start
&& isspace(*start
))
669 break; /* success, we hit the end */
671 /* 'out' is used to remove any back-quotes */
674 /* Everything apart from '\0' can be quoted */
675 if (*end
== '\\' && *(end
+ 1)) {
682 break; /* end of token */
687 /* have we already filled the array ? */
688 if ((*argc
+ 1) > array_size
) {
689 argv
= realloc_argv(&array_size
, argv
);
694 /* we know this is whitespace */
698 /* terminate the string and put it in the array */
708 static void check_for_valid_limits(struct io_restrictions
*rs
)
710 if (!rs
->max_sectors
)
711 rs
->max_sectors
= SAFE_MAX_SECTORS
;
712 if (!rs
->max_hw_sectors
)
713 rs
->max_hw_sectors
= SAFE_MAX_SECTORS
;
714 if (!rs
->max_phys_segments
)
715 rs
->max_phys_segments
= MAX_PHYS_SEGMENTS
;
716 if (!rs
->max_hw_segments
)
717 rs
->max_hw_segments
= MAX_HW_SEGMENTS
;
718 if (!rs
->hardsect_size
)
719 rs
->hardsect_size
= 1 << SECTOR_SHIFT
;
720 if (!rs
->max_segment_size
)
721 rs
->max_segment_size
= MAX_SEGMENT_SIZE
;
722 if (!rs
->seg_boundary_mask
)
723 rs
->seg_boundary_mask
= -1;
728 int dm_table_add_target(struct dm_table
*t
, const char *type
,
729 sector_t start
, sector_t len
, char *params
)
731 int r
= -EINVAL
, argc
;
733 struct dm_target
*tgt
;
735 if ((r
= check_space(t
)))
738 tgt
= t
->targets
+ t
->num_targets
;
739 memset(tgt
, 0, sizeof(*tgt
));
742 DMERR("%s: zero-length target", dm_device_name(t
->md
));
746 tgt
->type
= dm_get_target_type(type
);
748 DMERR("%s: %s: unknown target type", dm_device_name(t
->md
),
756 tgt
->error
= "Unknown error";
759 * Does this target adjoin the previous one ?
761 if (!adjoin(t
, tgt
)) {
762 tgt
->error
= "Gap in table";
767 r
= dm_split_args(&argc
, &argv
, params
);
769 tgt
->error
= "couldn't split parameters (insufficient memory)";
773 r
= tgt
->type
->ctr(tgt
, argc
, argv
);
778 t
->highs
[t
->num_targets
++] = tgt
->begin
+ tgt
->len
- 1;
780 /* FIXME: the plan is to combine high here and then have
781 * the merge fn apply the target level restrictions. */
782 combine_restrictions_low(&t
->limits
, &tgt
->limits
);
786 DMERR("%s: %s: %s", dm_device_name(t
->md
), type
, tgt
->error
);
787 dm_put_target_type(tgt
->type
);
791 static int setup_indexes(struct dm_table
*t
)
794 unsigned int total
= 0;
797 /* allocate the space for *all* the indexes */
798 for (i
= t
->depth
- 2; i
>= 0; i
--) {
799 t
->counts
[i
] = dm_div_up(t
->counts
[i
+ 1], CHILDREN_PER_NODE
);
800 total
+= t
->counts
[i
];
803 indexes
= (sector_t
*) dm_vcalloc(total
, (unsigned long) NODE_SIZE
);
807 /* set up internal nodes, bottom-up */
808 for (i
= t
->depth
- 2, total
= 0; i
>= 0; i
--) {
809 t
->index
[i
] = indexes
;
810 indexes
+= (KEYS_PER_NODE
* t
->counts
[i
]);
811 setup_btree_index(i
, t
);
818 * Builds the btree to index the map.
820 int dm_table_complete(struct dm_table
*t
)
823 unsigned int leaf_nodes
;
825 check_for_valid_limits(&t
->limits
);
827 /* how many indexes will the btree have ? */
828 leaf_nodes
= dm_div_up(t
->num_targets
, KEYS_PER_NODE
);
829 t
->depth
= 1 + int_log(leaf_nodes
, CHILDREN_PER_NODE
);
831 /* leaf layer has already been set up */
832 t
->counts
[t
->depth
- 1] = leaf_nodes
;
833 t
->index
[t
->depth
- 1] = t
->highs
;
836 r
= setup_indexes(t
);
841 static DEFINE_MUTEX(_event_lock
);
842 void dm_table_event_callback(struct dm_table
*t
,
843 void (*fn
)(void *), void *context
)
845 mutex_lock(&_event_lock
);
847 t
->event_context
= context
;
848 mutex_unlock(&_event_lock
);
851 void dm_table_event(struct dm_table
*t
)
854 * You can no longer call dm_table_event() from interrupt
855 * context, use a bottom half instead.
857 BUG_ON(in_interrupt());
859 mutex_lock(&_event_lock
);
861 t
->event_fn(t
->event_context
);
862 mutex_unlock(&_event_lock
);
865 sector_t
dm_table_get_size(struct dm_table
*t
)
867 return t
->num_targets
? (t
->highs
[t
->num_targets
- 1] + 1) : 0;
870 struct dm_target
*dm_table_get_target(struct dm_table
*t
, unsigned int index
)
872 if (index
>= t
->num_targets
)
875 return t
->targets
+ index
;
879 * Search the btree for the correct target.
881 * Caller should check returned pointer with dm_target_is_valid()
882 * to trap I/O beyond end of device.
884 struct dm_target
*dm_table_find_target(struct dm_table
*t
, sector_t sector
)
886 unsigned int l
, n
= 0, k
= 0;
889 for (l
= 0; l
< t
->depth
; l
++) {
891 node
= get_node(t
, l
, n
);
893 for (k
= 0; k
< KEYS_PER_NODE
; k
++)
894 if (node
[k
] >= sector
)
898 return &t
->targets
[(KEYS_PER_NODE
* n
) + k
];
901 void dm_table_set_restrictions(struct dm_table
*t
, struct request_queue
*q
)
904 * Make sure we obey the optimistic sub devices
907 blk_queue_max_sectors(q
, t
->limits
.max_sectors
);
908 q
->max_phys_segments
= t
->limits
.max_phys_segments
;
909 q
->max_hw_segments
= t
->limits
.max_hw_segments
;
910 q
->hardsect_size
= t
->limits
.hardsect_size
;
911 q
->max_segment_size
= t
->limits
.max_segment_size
;
912 q
->max_hw_sectors
= t
->limits
.max_hw_sectors
;
913 q
->seg_boundary_mask
= t
->limits
.seg_boundary_mask
;
914 q
->bounce_pfn
= t
->limits
.bounce_pfn
;
915 if (t
->limits
.no_cluster
)
916 q
->queue_flags
&= ~(1 << QUEUE_FLAG_CLUSTER
);
918 q
->queue_flags
|= (1 << QUEUE_FLAG_CLUSTER
);
922 unsigned int dm_table_get_num_targets(struct dm_table
*t
)
924 return t
->num_targets
;
927 struct list_head
*dm_table_get_devices(struct dm_table
*t
)
932 int dm_table_get_mode(struct dm_table
*t
)
937 static void suspend_targets(struct dm_table
*t
, unsigned postsuspend
)
939 int i
= t
->num_targets
;
940 struct dm_target
*ti
= t
->targets
;
944 if (ti
->type
->postsuspend
)
945 ti
->type
->postsuspend(ti
);
946 } else if (ti
->type
->presuspend
)
947 ti
->type
->presuspend(ti
);
953 void dm_table_presuspend_targets(struct dm_table
*t
)
958 return suspend_targets(t
, 0);
961 void dm_table_postsuspend_targets(struct dm_table
*t
)
966 return suspend_targets(t
, 1);
969 int dm_table_resume_targets(struct dm_table
*t
)
973 for (i
= 0; i
< t
->num_targets
; i
++) {
974 struct dm_target
*ti
= t
->targets
+ i
;
976 if (!ti
->type
->preresume
)
979 r
= ti
->type
->preresume(ti
);
984 for (i
= 0; i
< t
->num_targets
; i
++) {
985 struct dm_target
*ti
= t
->targets
+ i
;
987 if (ti
->type
->resume
)
988 ti
->type
->resume(ti
);
994 int dm_table_any_congested(struct dm_table
*t
, int bdi_bits
)
996 struct list_head
*d
, *devices
;
999 devices
= dm_table_get_devices(t
);
1000 for (d
= devices
->next
; d
!= devices
; d
= d
->next
) {
1001 struct dm_dev
*dd
= list_entry(d
, struct dm_dev
, list
);
1002 struct request_queue
*q
= bdev_get_queue(dd
->bdev
);
1003 r
|= bdi_congested(&q
->backing_dev_info
, bdi_bits
);
1009 void dm_table_unplug_all(struct dm_table
*t
)
1011 struct list_head
*d
, *devices
= dm_table_get_devices(t
);
1013 for (d
= devices
->next
; d
!= devices
; d
= d
->next
) {
1014 struct dm_dev
*dd
= list_entry(d
, struct dm_dev
, list
);
1015 struct request_queue
*q
= bdev_get_queue(dd
->bdev
);
1021 struct mapped_device
*dm_table_get_md(struct dm_table
*t
)
1028 EXPORT_SYMBOL(dm_vcalloc
);
1029 EXPORT_SYMBOL(dm_get_device
);
1030 EXPORT_SYMBOL(dm_put_device
);
1031 EXPORT_SYMBOL(dm_table_event
);
1032 EXPORT_SYMBOL(dm_table_get_size
);
1033 EXPORT_SYMBOL(dm_table_get_mode
);
1034 EXPORT_SYMBOL(dm_table_get_md
);
1035 EXPORT_SYMBOL(dm_table_put
);
1036 EXPORT_SYMBOL(dm_table_get
);
1037 EXPORT_SYMBOL(dm_table_unplug_all
);