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 static void free_devices(struct list_head
*devices
)
250 struct list_head
*tmp
, *next
;
252 list_for_each_safe(tmp
, next
, devices
) {
253 struct dm_dev
*dd
= list_entry(tmp
, struct dm_dev
, list
);
258 static void table_destroy(struct dm_table
*t
)
262 /* free the indexes (see dm_table_complete) */
264 vfree(t
->index
[t
->depth
- 2]);
266 /* free the targets */
267 for (i
= 0; i
< t
->num_targets
; i
++) {
268 struct dm_target
*tgt
= t
->targets
+ i
;
273 dm_put_target_type(tgt
->type
);
278 /* free the device list */
279 if (t
->devices
.next
!= &t
->devices
) {
280 DMWARN("devices still present during destroy: "
281 "dm_table_remove_device calls missing");
283 free_devices(&t
->devices
);
289 void dm_table_get(struct dm_table
*t
)
291 atomic_inc(&t
->holders
);
294 void dm_table_put(struct dm_table
*t
)
299 if (atomic_dec_and_test(&t
->holders
))
304 * Checks to see if we need to extend highs or targets.
306 static inline int check_space(struct dm_table
*t
)
308 if (t
->num_targets
>= t
->num_allocated
)
309 return alloc_targets(t
, t
->num_allocated
* 2);
315 * Convert a device path to a dev_t.
317 static int lookup_device(const char *path
, dev_t
*dev
)
319 struct block_device
*bdev
= lookup_bdev(path
);
321 return PTR_ERR(bdev
);
328 * See if we've already got a device in the list.
330 static struct dm_dev
*find_device(struct list_head
*l
, dev_t dev
)
334 list_for_each_entry (dd
, l
, list
)
335 if (dd
->bdev
->bd_dev
== dev
)
342 * Open a device so we can use it as a map destination.
344 static int open_dev(struct dm_dev
*d
, dev_t dev
, struct mapped_device
*md
)
346 static char *_claim_ptr
= "I belong to device-mapper";
347 struct block_device
*bdev
;
353 bdev
= open_by_devnum(dev
, d
->mode
);
355 return PTR_ERR(bdev
);
356 r
= bd_claim_by_disk(bdev
, _claim_ptr
, dm_disk(md
));
365 * Close a device that we've been using.
367 static void close_dev(struct dm_dev
*d
, struct mapped_device
*md
)
372 bd_release_from_disk(d
->bdev
, dm_disk(md
));
378 * If possible, this checks an area of a destination device is valid.
380 static int check_device_area(struct dm_dev
*dd
, sector_t start
, sector_t len
)
382 sector_t dev_size
= dd
->bdev
->bd_inode
->i_size
>> SECTOR_SHIFT
;
387 return ((start
< dev_size
) && (len
<= (dev_size
- start
)));
391 * This upgrades the mode on an already open dm_dev. Being
392 * careful to leave things as they were if we fail to reopen the
395 static int upgrade_mode(struct dm_dev
*dd
, int new_mode
, struct mapped_device
*md
)
398 struct dm_dev dd_copy
;
399 dev_t dev
= dd
->bdev
->bd_dev
;
403 dd
->mode
|= new_mode
;
405 r
= open_dev(dd
, dev
, md
);
407 close_dev(&dd_copy
, md
);
415 * Add a device to the list, or just increment the usage count if
416 * it's already present.
418 static int __table_get_device(struct dm_table
*t
, struct dm_target
*ti
,
419 const char *path
, sector_t start
, sector_t len
,
420 int mode
, struct dm_dev
**result
)
423 dev_t
uninitialized_var(dev
);
425 unsigned int major
, minor
;
429 if (sscanf(path
, "%u:%u", &major
, &minor
) == 2) {
430 /* Extract the major/minor numbers */
431 dev
= MKDEV(major
, minor
);
432 if (MAJOR(dev
) != major
|| MINOR(dev
) != minor
)
435 /* convert the path to a device */
436 if ((r
= lookup_device(path
, &dev
)))
440 dd
= find_device(&t
->devices
, dev
);
442 dd
= kmalloc(sizeof(*dd
), GFP_KERNEL
);
449 if ((r
= open_dev(dd
, dev
, t
->md
))) {
454 format_dev_t(dd
->name
, dev
);
456 atomic_set(&dd
->count
, 0);
457 list_add(&dd
->list
, &t
->devices
);
459 } else if (dd
->mode
!= (mode
| dd
->mode
)) {
460 r
= upgrade_mode(dd
, mode
, t
->md
);
464 atomic_inc(&dd
->count
);
466 if (!check_device_area(dd
, start
, len
)) {
467 DMWARN("device %s too small for target", path
);
468 dm_put_device(ti
, dd
);
477 void dm_set_device_limits(struct dm_target
*ti
, struct block_device
*bdev
)
479 struct request_queue
*q
= bdev_get_queue(bdev
);
480 struct io_restrictions
*rs
= &ti
->limits
;
483 * Combine the device limits low.
485 * FIXME: if we move an io_restriction struct
486 * into q this would just be a call to
487 * combine_restrictions_low()
490 min_not_zero(rs
->max_sectors
, q
->max_sectors
);
493 * Check if merge fn is supported.
494 * If not we'll force DM to use PAGE_SIZE or
495 * smaller I/O, just to be safe.
498 if (q
->merge_bvec_fn
&& !ti
->type
->merge
)
500 min_not_zero(rs
->max_sectors
,
501 (unsigned int) (PAGE_SIZE
>> 9));
503 rs
->max_phys_segments
=
504 min_not_zero(rs
->max_phys_segments
,
505 q
->max_phys_segments
);
507 rs
->max_hw_segments
=
508 min_not_zero(rs
->max_hw_segments
, q
->max_hw_segments
);
510 rs
->hardsect_size
= max(rs
->hardsect_size
, q
->hardsect_size
);
512 rs
->max_segment_size
=
513 min_not_zero(rs
->max_segment_size
, q
->max_segment_size
);
516 min_not_zero(rs
->max_hw_sectors
, q
->max_hw_sectors
);
518 rs
->seg_boundary_mask
=
519 min_not_zero(rs
->seg_boundary_mask
,
520 q
->seg_boundary_mask
);
522 rs
->bounce_pfn
= min_not_zero(rs
->bounce_pfn
, q
->bounce_pfn
);
524 rs
->no_cluster
|= !test_bit(QUEUE_FLAG_CLUSTER
, &q
->queue_flags
);
526 EXPORT_SYMBOL_GPL(dm_set_device_limits
);
528 int dm_get_device(struct dm_target
*ti
, const char *path
, sector_t start
,
529 sector_t len
, int mode
, struct dm_dev
**result
)
531 int r
= __table_get_device(ti
->table
, ti
, path
,
532 start
, len
, mode
, result
);
535 dm_set_device_limits(ti
, (*result
)->bdev
);
541 * Decrement a devices use count and remove it if necessary.
543 void dm_put_device(struct dm_target
*ti
, struct dm_dev
*dd
)
545 if (atomic_dec_and_test(&dd
->count
)) {
546 close_dev(dd
, ti
->table
->md
);
553 * Checks to see if the target joins onto the end of the table.
555 static int adjoin(struct dm_table
*table
, struct dm_target
*ti
)
557 struct dm_target
*prev
;
559 if (!table
->num_targets
)
562 prev
= &table
->targets
[table
->num_targets
- 1];
563 return (ti
->begin
== (prev
->begin
+ prev
->len
));
567 * Used to dynamically allocate the arg array.
569 static char **realloc_argv(unsigned *array_size
, char **old_argv
)
574 new_size
= *array_size
? *array_size
* 2 : 64;
575 argv
= kmalloc(new_size
* sizeof(*argv
), GFP_KERNEL
);
577 memcpy(argv
, old_argv
, *array_size
* sizeof(*argv
));
578 *array_size
= new_size
;
586 * Destructively splits up the argument list to pass to ctr.
588 int dm_split_args(int *argc
, char ***argvp
, char *input
)
590 char *start
, *end
= input
, *out
, **argv
= NULL
;
591 unsigned array_size
= 0;
600 argv
= realloc_argv(&array_size
, argv
);
607 /* Skip whitespace */
608 while (*start
&& isspace(*start
))
612 break; /* success, we hit the end */
614 /* 'out' is used to remove any back-quotes */
617 /* Everything apart from '\0' can be quoted */
618 if (*end
== '\\' && *(end
+ 1)) {
625 break; /* end of token */
630 /* have we already filled the array ? */
631 if ((*argc
+ 1) > array_size
) {
632 argv
= realloc_argv(&array_size
, argv
);
637 /* we know this is whitespace */
641 /* terminate the string and put it in the array */
651 static void check_for_valid_limits(struct io_restrictions
*rs
)
653 if (!rs
->max_sectors
)
654 rs
->max_sectors
= SAFE_MAX_SECTORS
;
655 if (!rs
->max_hw_sectors
)
656 rs
->max_hw_sectors
= SAFE_MAX_SECTORS
;
657 if (!rs
->max_phys_segments
)
658 rs
->max_phys_segments
= MAX_PHYS_SEGMENTS
;
659 if (!rs
->max_hw_segments
)
660 rs
->max_hw_segments
= MAX_HW_SEGMENTS
;
661 if (!rs
->hardsect_size
)
662 rs
->hardsect_size
= 1 << SECTOR_SHIFT
;
663 if (!rs
->max_segment_size
)
664 rs
->max_segment_size
= MAX_SEGMENT_SIZE
;
665 if (!rs
->seg_boundary_mask
)
666 rs
->seg_boundary_mask
= -1;
671 int dm_table_add_target(struct dm_table
*t
, const char *type
,
672 sector_t start
, sector_t len
, char *params
)
674 int r
= -EINVAL
, argc
;
676 struct dm_target
*tgt
;
678 if ((r
= check_space(t
)))
681 tgt
= t
->targets
+ t
->num_targets
;
682 memset(tgt
, 0, sizeof(*tgt
));
685 DMERR("%s: zero-length target", dm_device_name(t
->md
));
689 tgt
->type
= dm_get_target_type(type
);
691 DMERR("%s: %s: unknown target type", dm_device_name(t
->md
),
699 tgt
->error
= "Unknown error";
702 * Does this target adjoin the previous one ?
704 if (!adjoin(t
, tgt
)) {
705 tgt
->error
= "Gap in table";
710 r
= dm_split_args(&argc
, &argv
, params
);
712 tgt
->error
= "couldn't split parameters (insufficient memory)";
716 r
= tgt
->type
->ctr(tgt
, argc
, argv
);
721 t
->highs
[t
->num_targets
++] = tgt
->begin
+ tgt
->len
- 1;
723 /* FIXME: the plan is to combine high here and then have
724 * the merge fn apply the target level restrictions. */
725 combine_restrictions_low(&t
->limits
, &tgt
->limits
);
729 DMERR("%s: %s: %s", dm_device_name(t
->md
), type
, tgt
->error
);
730 dm_put_target_type(tgt
->type
);
734 static int setup_indexes(struct dm_table
*t
)
737 unsigned int total
= 0;
740 /* allocate the space for *all* the indexes */
741 for (i
= t
->depth
- 2; i
>= 0; i
--) {
742 t
->counts
[i
] = dm_div_up(t
->counts
[i
+ 1], CHILDREN_PER_NODE
);
743 total
+= t
->counts
[i
];
746 indexes
= (sector_t
*) dm_vcalloc(total
, (unsigned long) NODE_SIZE
);
750 /* set up internal nodes, bottom-up */
751 for (i
= t
->depth
- 2; i
>= 0; i
--) {
752 t
->index
[i
] = indexes
;
753 indexes
+= (KEYS_PER_NODE
* t
->counts
[i
]);
754 setup_btree_index(i
, t
);
761 * Builds the btree to index the map.
763 int dm_table_complete(struct dm_table
*t
)
766 unsigned int leaf_nodes
;
768 check_for_valid_limits(&t
->limits
);
770 /* how many indexes will the btree have ? */
771 leaf_nodes
= dm_div_up(t
->num_targets
, KEYS_PER_NODE
);
772 t
->depth
= 1 + int_log(leaf_nodes
, CHILDREN_PER_NODE
);
774 /* leaf layer has already been set up */
775 t
->counts
[t
->depth
- 1] = leaf_nodes
;
776 t
->index
[t
->depth
- 1] = t
->highs
;
779 r
= setup_indexes(t
);
784 static DEFINE_MUTEX(_event_lock
);
785 void dm_table_event_callback(struct dm_table
*t
,
786 void (*fn
)(void *), void *context
)
788 mutex_lock(&_event_lock
);
790 t
->event_context
= context
;
791 mutex_unlock(&_event_lock
);
794 void dm_table_event(struct dm_table
*t
)
797 * You can no longer call dm_table_event() from interrupt
798 * context, use a bottom half instead.
800 BUG_ON(in_interrupt());
802 mutex_lock(&_event_lock
);
804 t
->event_fn(t
->event_context
);
805 mutex_unlock(&_event_lock
);
808 sector_t
dm_table_get_size(struct dm_table
*t
)
810 return t
->num_targets
? (t
->highs
[t
->num_targets
- 1] + 1) : 0;
813 struct dm_target
*dm_table_get_target(struct dm_table
*t
, unsigned int index
)
815 if (index
>= t
->num_targets
)
818 return t
->targets
+ index
;
822 * Search the btree for the correct target.
824 * Caller should check returned pointer with dm_target_is_valid()
825 * to trap I/O beyond end of device.
827 struct dm_target
*dm_table_find_target(struct dm_table
*t
, sector_t sector
)
829 unsigned int l
, n
= 0, k
= 0;
832 for (l
= 0; l
< t
->depth
; l
++) {
834 node
= get_node(t
, l
, n
);
836 for (k
= 0; k
< KEYS_PER_NODE
; k
++)
837 if (node
[k
] >= sector
)
841 return &t
->targets
[(KEYS_PER_NODE
* n
) + k
];
844 void dm_table_set_restrictions(struct dm_table
*t
, struct request_queue
*q
)
847 * Make sure we obey the optimistic sub devices
850 blk_queue_max_sectors(q
, t
->limits
.max_sectors
);
851 q
->max_phys_segments
= t
->limits
.max_phys_segments
;
852 q
->max_hw_segments
= t
->limits
.max_hw_segments
;
853 q
->hardsect_size
= t
->limits
.hardsect_size
;
854 q
->max_segment_size
= t
->limits
.max_segment_size
;
855 q
->max_hw_sectors
= t
->limits
.max_hw_sectors
;
856 q
->seg_boundary_mask
= t
->limits
.seg_boundary_mask
;
857 q
->bounce_pfn
= t
->limits
.bounce_pfn
;
859 if (t
->limits
.no_cluster
)
860 queue_flag_clear_unlocked(QUEUE_FLAG_CLUSTER
, q
);
862 queue_flag_set_unlocked(QUEUE_FLAG_CLUSTER
, q
);
866 unsigned int dm_table_get_num_targets(struct dm_table
*t
)
868 return t
->num_targets
;
871 struct list_head
*dm_table_get_devices(struct dm_table
*t
)
876 int dm_table_get_mode(struct dm_table
*t
)
881 static void suspend_targets(struct dm_table
*t
, unsigned postsuspend
)
883 int i
= t
->num_targets
;
884 struct dm_target
*ti
= t
->targets
;
888 if (ti
->type
->postsuspend
)
889 ti
->type
->postsuspend(ti
);
890 } else if (ti
->type
->presuspend
)
891 ti
->type
->presuspend(ti
);
897 void dm_table_presuspend_targets(struct dm_table
*t
)
902 suspend_targets(t
, 0);
905 void dm_table_postsuspend_targets(struct dm_table
*t
)
910 suspend_targets(t
, 1);
913 int dm_table_resume_targets(struct dm_table
*t
)
917 for (i
= 0; i
< t
->num_targets
; i
++) {
918 struct dm_target
*ti
= t
->targets
+ i
;
920 if (!ti
->type
->preresume
)
923 r
= ti
->type
->preresume(ti
);
928 for (i
= 0; i
< t
->num_targets
; i
++) {
929 struct dm_target
*ti
= t
->targets
+ i
;
931 if (ti
->type
->resume
)
932 ti
->type
->resume(ti
);
938 int dm_table_any_congested(struct dm_table
*t
, int bdi_bits
)
941 struct list_head
*devices
= dm_table_get_devices(t
);
944 list_for_each_entry(dd
, devices
, list
) {
945 struct request_queue
*q
= bdev_get_queue(dd
->bdev
);
946 r
|= bdi_congested(&q
->backing_dev_info
, bdi_bits
);
952 void dm_table_unplug_all(struct dm_table
*t
)
955 struct list_head
*devices
= dm_table_get_devices(t
);
957 list_for_each_entry(dd
, devices
, list
) {
958 struct request_queue
*q
= bdev_get_queue(dd
->bdev
);
964 struct mapped_device
*dm_table_get_md(struct dm_table
*t
)
971 EXPORT_SYMBOL(dm_vcalloc
);
972 EXPORT_SYMBOL(dm_get_device
);
973 EXPORT_SYMBOL(dm_put_device
);
974 EXPORT_SYMBOL(dm_table_event
);
975 EXPORT_SYMBOL(dm_table_get_size
);
976 EXPORT_SYMBOL(dm_table_get_mode
);
977 EXPORT_SYMBOL(dm_table_get_md
);
978 EXPORT_SYMBOL(dm_table_put
);
979 EXPORT_SYMBOL(dm_table_get
);
980 EXPORT_SYMBOL(dm_table_unplug_all
);