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>
21 #define NODE_SIZE L1_CACHE_BYTES
22 #define KEYS_PER_NODE (NODE_SIZE / sizeof(sector_t))
23 #define CHILDREN_PER_NODE (KEYS_PER_NODE + 1)
26 struct mapped_device
*md
;
31 unsigned int counts
[MAX_DEPTH
]; /* in nodes */
32 sector_t
*index
[MAX_DEPTH
];
34 unsigned int num_targets
;
35 unsigned int num_allocated
;
37 struct dm_target
*targets
;
40 * Indicates the rw permissions for the new logical
41 * device. This should be a combination of FMODE_READ
46 /* a list of devices used by this table */
47 struct list_head devices
;
50 * These are optimistic limits taken from all the
51 * targets, some targets will need smaller limits.
53 struct io_restrictions limits
;
55 /* events get handed up using this callback */
56 void (*event_fn
)(void *);
61 * Similar to ceiling(log_size(n))
63 static unsigned int int_log(unsigned int n
, unsigned int base
)
68 n
= dm_div_up(n
, base
);
76 * Returns the minimum that is _not_ zero, unless both are zero.
78 #define min_not_zero(l, r) (l == 0) ? r : ((r == 0) ? l : min(l, r))
81 * Combine two io_restrictions, always taking the lower value.
83 static void combine_restrictions_low(struct io_restrictions
*lhs
,
84 struct io_restrictions
*rhs
)
87 min_not_zero(lhs
->max_sectors
, rhs
->max_sectors
);
89 lhs
->max_phys_segments
=
90 min_not_zero(lhs
->max_phys_segments
, rhs
->max_phys_segments
);
92 lhs
->max_hw_segments
=
93 min_not_zero(lhs
->max_hw_segments
, rhs
->max_hw_segments
);
95 lhs
->hardsect_size
= max(lhs
->hardsect_size
, rhs
->hardsect_size
);
97 lhs
->max_segment_size
=
98 min_not_zero(lhs
->max_segment_size
, rhs
->max_segment_size
);
100 lhs
->seg_boundary_mask
=
101 min_not_zero(lhs
->seg_boundary_mask
, rhs
->seg_boundary_mask
);
103 lhs
->no_cluster
|= rhs
->no_cluster
;
107 * Calculate the index of the child node of the n'th node k'th key.
109 static inline unsigned int get_child(unsigned int n
, unsigned int k
)
111 return (n
* CHILDREN_PER_NODE
) + k
;
115 * Return the n'th node of level l from table t.
117 static inline sector_t
*get_node(struct dm_table
*t
,
118 unsigned int l
, unsigned int n
)
120 return t
->index
[l
] + (n
* KEYS_PER_NODE
);
124 * Return the highest key that you could lookup from the n'th
125 * node on level l of the btree.
127 static sector_t
high(struct dm_table
*t
, unsigned int l
, unsigned int n
)
129 for (; l
< t
->depth
- 1; l
++)
130 n
= get_child(n
, CHILDREN_PER_NODE
- 1);
132 if (n
>= t
->counts
[l
])
133 return (sector_t
) - 1;
135 return get_node(t
, l
, n
)[KEYS_PER_NODE
- 1];
139 * Fills in a level of the btree based on the highs of the level
142 static int setup_btree_index(unsigned int l
, struct dm_table
*t
)
147 for (n
= 0U; n
< t
->counts
[l
]; n
++) {
148 node
= get_node(t
, l
, n
);
150 for (k
= 0U; k
< KEYS_PER_NODE
; k
++)
151 node
[k
] = high(t
, l
+ 1, get_child(n
, k
));
157 void *dm_vcalloc(unsigned long nmemb
, unsigned long elem_size
)
163 * Check that we're not going to overflow.
165 if (nmemb
> (ULONG_MAX
/ elem_size
))
168 size
= nmemb
* elem_size
;
169 addr
= vmalloc(size
);
171 memset(addr
, 0, size
);
177 * highs, and targets are managed as dynamic arrays during a
180 static int alloc_targets(struct dm_table
*t
, unsigned int num
)
183 struct dm_target
*n_targets
;
184 int n
= t
->num_targets
;
187 * Allocate both the target array and offset array at once.
189 n_highs
= (sector_t
*) dm_vcalloc(num
, sizeof(struct dm_target
) +
194 n_targets
= (struct dm_target
*) (n_highs
+ num
);
197 memcpy(n_highs
, t
->highs
, sizeof(*n_highs
) * n
);
198 memcpy(n_targets
, t
->targets
, sizeof(*n_targets
) * n
);
201 memset(n_highs
+ n
, -1, sizeof(*n_highs
) * (num
- n
));
204 t
->num_allocated
= num
;
206 t
->targets
= n_targets
;
211 int dm_table_create(struct dm_table
**result
, int mode
,
212 unsigned num_targets
, struct mapped_device
*md
)
214 struct dm_table
*t
= kmalloc(sizeof(*t
), GFP_KERNEL
);
219 memset(t
, 0, sizeof(*t
));
220 INIT_LIST_HEAD(&t
->devices
);
221 atomic_set(&t
->holders
, 1);
224 num_targets
= KEYS_PER_NODE
;
226 num_targets
= dm_round_up(num_targets
, KEYS_PER_NODE
);
228 if (alloc_targets(t
, num_targets
)) {
240 static void free_devices(struct list_head
*devices
)
242 struct list_head
*tmp
, *next
;
244 for (tmp
= devices
->next
; tmp
!= devices
; tmp
= next
) {
245 struct dm_dev
*dd
= list_entry(tmp
, struct dm_dev
, list
);
251 static void table_destroy(struct dm_table
*t
)
255 /* free the indexes (see dm_table_complete) */
257 vfree(t
->index
[t
->depth
- 2]);
259 /* free the targets */
260 for (i
= 0; i
< t
->num_targets
; i
++) {
261 struct dm_target
*tgt
= t
->targets
+ i
;
266 dm_put_target_type(tgt
->type
);
271 /* free the device list */
272 if (t
->devices
.next
!= &t
->devices
) {
273 DMWARN("devices still present during destroy: "
274 "dm_table_remove_device calls missing");
276 free_devices(&t
->devices
);
282 void dm_table_get(struct dm_table
*t
)
284 atomic_inc(&t
->holders
);
287 void dm_table_put(struct dm_table
*t
)
292 if (atomic_dec_and_test(&t
->holders
))
297 * Checks to see if we need to extend highs or targets.
299 static inline int check_space(struct dm_table
*t
)
301 if (t
->num_targets
>= t
->num_allocated
)
302 return alloc_targets(t
, t
->num_allocated
* 2);
308 * Convert a device path to a dev_t.
310 static int lookup_device(const char *path
, dev_t
*dev
)
316 if ((r
= path_lookup(path
, LOOKUP_FOLLOW
, &nd
)))
319 inode
= nd
.dentry
->d_inode
;
325 if (!S_ISBLK(inode
->i_mode
)) {
330 *dev
= inode
->i_rdev
;
338 * See if we've already got a device in the list.
340 static struct dm_dev
*find_device(struct list_head
*l
, dev_t dev
)
344 list_for_each_entry (dd
, l
, list
)
345 if (dd
->bdev
->bd_dev
== dev
)
352 * Open a device so we can use it as a map destination.
354 static int open_dev(struct dm_dev
*d
, dev_t dev
, struct mapped_device
*md
)
356 static char *_claim_ptr
= "I belong to device-mapper";
357 struct block_device
*bdev
;
363 bdev
= open_by_devnum(dev
, d
->mode
);
365 return PTR_ERR(bdev
);
366 r
= bd_claim_by_disk(bdev
, _claim_ptr
, dm_disk(md
));
375 * Close a device that we've been using.
377 static void close_dev(struct dm_dev
*d
, struct mapped_device
*md
)
382 bd_release_from_disk(d
->bdev
, dm_disk(md
));
388 * If possible (ie. blk_size[major] is set), this checks an area
389 * of a destination device is valid.
391 static int check_device_area(struct dm_dev
*dd
, sector_t start
, sector_t len
)
394 dev_size
= dd
->bdev
->bd_inode
->i_size
>> SECTOR_SHIFT
;
395 return ((start
< dev_size
) && (len
<= (dev_size
- start
)));
399 * This upgrades the mode on an already open dm_dev. Being
400 * careful to leave things as they were if we fail to reopen the
403 static int upgrade_mode(struct dm_dev
*dd
, int new_mode
, struct mapped_device
*md
)
406 struct dm_dev dd_copy
;
407 dev_t dev
= dd
->bdev
->bd_dev
;
411 dd
->mode
|= new_mode
;
413 r
= open_dev(dd
, dev
, md
);
415 close_dev(&dd_copy
, md
);
423 * Add a device to the list, or just increment the usage count if
424 * it's already present.
426 static int __table_get_device(struct dm_table
*t
, struct dm_target
*ti
,
427 const char *path
, sector_t start
, sector_t len
,
428 int mode
, struct dm_dev
**result
)
433 unsigned int major
, minor
;
437 if (sscanf(path
, "%u:%u", &major
, &minor
) == 2) {
438 /* Extract the major/minor numbers */
439 dev
= MKDEV(major
, minor
);
440 if (MAJOR(dev
) != major
|| MINOR(dev
) != minor
)
443 /* convert the path to a device */
444 if ((r
= lookup_device(path
, &dev
)))
448 dd
= find_device(&t
->devices
, dev
);
450 dd
= kmalloc(sizeof(*dd
), GFP_KERNEL
);
457 if ((r
= open_dev(dd
, dev
, t
->md
))) {
462 format_dev_t(dd
->name
, dev
);
464 atomic_set(&dd
->count
, 0);
465 list_add(&dd
->list
, &t
->devices
);
467 } else if (dd
->mode
!= (mode
| dd
->mode
)) {
468 r
= upgrade_mode(dd
, mode
, t
->md
);
472 atomic_inc(&dd
->count
);
474 if (!check_device_area(dd
, start
, len
)) {
475 DMWARN("device %s too small for target", path
);
476 dm_put_device(ti
, dd
);
486 int dm_get_device(struct dm_target
*ti
, const char *path
, sector_t start
,
487 sector_t len
, int mode
, struct dm_dev
**result
)
489 int r
= __table_get_device(ti
->table
, ti
, path
,
490 start
, len
, mode
, result
);
492 request_queue_t
*q
= bdev_get_queue((*result
)->bdev
);
493 struct io_restrictions
*rs
= &ti
->limits
;
496 * Combine the device limits low.
498 * FIXME: if we move an io_restriction struct
499 * into q this would just be a call to
500 * combine_restrictions_low()
503 min_not_zero(rs
->max_sectors
, q
->max_sectors
);
505 /* FIXME: Device-Mapper on top of RAID-0 breaks because DM
506 * currently doesn't honor MD's merge_bvec_fn routine.
507 * In this case, we'll force DM to use PAGE_SIZE or
508 * smaller I/O, just to be safe. A better fix is in the
509 * works, but add this for the time being so it will at
510 * least operate correctly.
512 if (q
->merge_bvec_fn
)
514 min_not_zero(rs
->max_sectors
,
515 (unsigned int) (PAGE_SIZE
>> 9));
517 rs
->max_phys_segments
=
518 min_not_zero(rs
->max_phys_segments
,
519 q
->max_phys_segments
);
521 rs
->max_hw_segments
=
522 min_not_zero(rs
->max_hw_segments
, q
->max_hw_segments
);
524 rs
->hardsect_size
= max(rs
->hardsect_size
, q
->hardsect_size
);
526 rs
->max_segment_size
=
527 min_not_zero(rs
->max_segment_size
, q
->max_segment_size
);
529 rs
->seg_boundary_mask
=
530 min_not_zero(rs
->seg_boundary_mask
,
531 q
->seg_boundary_mask
);
533 rs
->no_cluster
|= !test_bit(QUEUE_FLAG_CLUSTER
, &q
->queue_flags
);
540 * Decrement a devices use count and remove it if necessary.
542 void dm_put_device(struct dm_target
*ti
, struct dm_dev
*dd
)
544 if (atomic_dec_and_test(&dd
->count
)) {
545 close_dev(dd
, ti
->table
->md
);
552 * Checks to see if the target joins onto the end of the table.
554 static int adjoin(struct dm_table
*table
, struct dm_target
*ti
)
556 struct dm_target
*prev
;
558 if (!table
->num_targets
)
561 prev
= &table
->targets
[table
->num_targets
- 1];
562 return (ti
->begin
== (prev
->begin
+ prev
->len
));
566 * Used to dynamically allocate the arg array.
568 static char **realloc_argv(unsigned *array_size
, char **old_argv
)
573 new_size
= *array_size
? *array_size
* 2 : 64;
574 argv
= kmalloc(new_size
* sizeof(*argv
), GFP_KERNEL
);
576 memcpy(argv
, old_argv
, *array_size
* sizeof(*argv
));
577 *array_size
= new_size
;
585 * Destructively splits up the argument list to pass to ctr.
587 int dm_split_args(int *argc
, char ***argvp
, char *input
)
589 char *start
, *end
= input
, *out
, **argv
= NULL
;
590 unsigned array_size
= 0;
593 argv
= realloc_argv(&array_size
, argv
);
600 /* Skip whitespace */
601 while (*start
&& isspace(*start
))
605 break; /* success, we hit the end */
607 /* 'out' is used to remove any back-quotes */
610 /* Everything apart from '\0' can be quoted */
611 if (*end
== '\\' && *(end
+ 1)) {
618 break; /* end of token */
623 /* have we already filled the array ? */
624 if ((*argc
+ 1) > array_size
) {
625 argv
= realloc_argv(&array_size
, argv
);
630 /* we know this is whitespace */
634 /* terminate the string and put it in the array */
644 static void check_for_valid_limits(struct io_restrictions
*rs
)
646 if (!rs
->max_sectors
)
647 rs
->max_sectors
= SAFE_MAX_SECTORS
;
648 if (!rs
->max_phys_segments
)
649 rs
->max_phys_segments
= MAX_PHYS_SEGMENTS
;
650 if (!rs
->max_hw_segments
)
651 rs
->max_hw_segments
= MAX_HW_SEGMENTS
;
652 if (!rs
->hardsect_size
)
653 rs
->hardsect_size
= 1 << SECTOR_SHIFT
;
654 if (!rs
->max_segment_size
)
655 rs
->max_segment_size
= MAX_SEGMENT_SIZE
;
656 if (!rs
->seg_boundary_mask
)
657 rs
->seg_boundary_mask
= -1;
660 int dm_table_add_target(struct dm_table
*t
, const char *type
,
661 sector_t start
, sector_t len
, char *params
)
663 int r
= -EINVAL
, argc
;
665 struct dm_target
*tgt
;
667 if ((r
= check_space(t
)))
670 tgt
= t
->targets
+ t
->num_targets
;
671 memset(tgt
, 0, sizeof(*tgt
));
674 tgt
->error
= "zero-length target";
675 DMERR("%s", tgt
->error
);
679 tgt
->type
= dm_get_target_type(type
);
681 tgt
->error
= "unknown target type";
682 DMERR("%s", tgt
->error
);
689 tgt
->error
= "Unknown error";
692 * Does this target adjoin the previous one ?
694 if (!adjoin(t
, tgt
)) {
695 tgt
->error
= "Gap in table";
700 r
= dm_split_args(&argc
, &argv
, params
);
702 tgt
->error
= "couldn't split parameters (insufficient memory)";
706 r
= tgt
->type
->ctr(tgt
, argc
, argv
);
711 t
->highs
[t
->num_targets
++] = tgt
->begin
+ tgt
->len
- 1;
713 /* FIXME: the plan is to combine high here and then have
714 * the merge fn apply the target level restrictions. */
715 combine_restrictions_low(&t
->limits
, &tgt
->limits
);
719 DMERR("%s", tgt
->error
);
720 dm_put_target_type(tgt
->type
);
724 static int setup_indexes(struct dm_table
*t
)
727 unsigned int total
= 0;
730 /* allocate the space for *all* the indexes */
731 for (i
= t
->depth
- 2; i
>= 0; i
--) {
732 t
->counts
[i
] = dm_div_up(t
->counts
[i
+ 1], CHILDREN_PER_NODE
);
733 total
+= t
->counts
[i
];
736 indexes
= (sector_t
*) dm_vcalloc(total
, (unsigned long) NODE_SIZE
);
740 /* set up internal nodes, bottom-up */
741 for (i
= t
->depth
- 2, total
= 0; i
>= 0; i
--) {
742 t
->index
[i
] = indexes
;
743 indexes
+= (KEYS_PER_NODE
* t
->counts
[i
]);
744 setup_btree_index(i
, t
);
751 * Builds the btree to index the map.
753 int dm_table_complete(struct dm_table
*t
)
756 unsigned int leaf_nodes
;
758 check_for_valid_limits(&t
->limits
);
760 /* how many indexes will the btree have ? */
761 leaf_nodes
= dm_div_up(t
->num_targets
, KEYS_PER_NODE
);
762 t
->depth
= 1 + int_log(leaf_nodes
, CHILDREN_PER_NODE
);
764 /* leaf layer has already been set up */
765 t
->counts
[t
->depth
- 1] = leaf_nodes
;
766 t
->index
[t
->depth
- 1] = t
->highs
;
769 r
= setup_indexes(t
);
774 static DEFINE_MUTEX(_event_lock
);
775 void dm_table_event_callback(struct dm_table
*t
,
776 void (*fn
)(void *), void *context
)
778 mutex_lock(&_event_lock
);
780 t
->event_context
= context
;
781 mutex_unlock(&_event_lock
);
784 void dm_table_event(struct dm_table
*t
)
787 * You can no longer call dm_table_event() from interrupt
788 * context, use a bottom half instead.
790 BUG_ON(in_interrupt());
792 mutex_lock(&_event_lock
);
794 t
->event_fn(t
->event_context
);
795 mutex_unlock(&_event_lock
);
798 sector_t
dm_table_get_size(struct dm_table
*t
)
800 return t
->num_targets
? (t
->highs
[t
->num_targets
- 1] + 1) : 0;
803 struct dm_target
*dm_table_get_target(struct dm_table
*t
, unsigned int index
)
805 if (index
> t
->num_targets
)
808 return t
->targets
+ index
;
812 * Search the btree for the correct target.
814 struct dm_target
*dm_table_find_target(struct dm_table
*t
, sector_t sector
)
816 unsigned int l
, n
= 0, k
= 0;
819 for (l
= 0; l
< t
->depth
; l
++) {
821 node
= get_node(t
, l
, n
);
823 for (k
= 0; k
< KEYS_PER_NODE
; k
++)
824 if (node
[k
] >= sector
)
828 return &t
->targets
[(KEYS_PER_NODE
* n
) + k
];
831 void dm_table_set_restrictions(struct dm_table
*t
, struct request_queue
*q
)
834 * Make sure we obey the optimistic sub devices
837 blk_queue_max_sectors(q
, t
->limits
.max_sectors
);
838 q
->max_phys_segments
= t
->limits
.max_phys_segments
;
839 q
->max_hw_segments
= t
->limits
.max_hw_segments
;
840 q
->hardsect_size
= t
->limits
.hardsect_size
;
841 q
->max_segment_size
= t
->limits
.max_segment_size
;
842 q
->seg_boundary_mask
= t
->limits
.seg_boundary_mask
;
843 if (t
->limits
.no_cluster
)
844 q
->queue_flags
&= ~(1 << QUEUE_FLAG_CLUSTER
);
846 q
->queue_flags
|= (1 << QUEUE_FLAG_CLUSTER
);
850 unsigned int dm_table_get_num_targets(struct dm_table
*t
)
852 return t
->num_targets
;
855 struct list_head
*dm_table_get_devices(struct dm_table
*t
)
860 int dm_table_get_mode(struct dm_table
*t
)
865 static void suspend_targets(struct dm_table
*t
, unsigned postsuspend
)
867 int i
= t
->num_targets
;
868 struct dm_target
*ti
= t
->targets
;
872 if (ti
->type
->postsuspend
)
873 ti
->type
->postsuspend(ti
);
874 } else if (ti
->type
->presuspend
)
875 ti
->type
->presuspend(ti
);
881 void dm_table_presuspend_targets(struct dm_table
*t
)
886 return suspend_targets(t
, 0);
889 void dm_table_postsuspend_targets(struct dm_table
*t
)
894 return suspend_targets(t
, 1);
897 void dm_table_resume_targets(struct dm_table
*t
)
901 for (i
= 0; i
< t
->num_targets
; i
++) {
902 struct dm_target
*ti
= t
->targets
+ i
;
904 if (ti
->type
->resume
)
905 ti
->type
->resume(ti
);
909 int dm_table_any_congested(struct dm_table
*t
, int bdi_bits
)
911 struct list_head
*d
, *devices
;
914 devices
= dm_table_get_devices(t
);
915 for (d
= devices
->next
; d
!= devices
; d
= d
->next
) {
916 struct dm_dev
*dd
= list_entry(d
, struct dm_dev
, list
);
917 request_queue_t
*q
= bdev_get_queue(dd
->bdev
);
918 r
|= bdi_congested(&q
->backing_dev_info
, bdi_bits
);
924 void dm_table_unplug_all(struct dm_table
*t
)
926 struct list_head
*d
, *devices
= dm_table_get_devices(t
);
928 for (d
= devices
->next
; d
!= devices
; d
= d
->next
) {
929 struct dm_dev
*dd
= list_entry(d
, struct dm_dev
, list
);
930 request_queue_t
*q
= bdev_get_queue(dd
->bdev
);
937 int dm_table_flush_all(struct dm_table
*t
)
939 struct list_head
*d
, *devices
= dm_table_get_devices(t
);
942 for (d
= devices
->next
; d
!= devices
; d
= d
->next
) {
943 struct dm_dev
*dd
= list_entry(d
, struct dm_dev
, list
);
944 request_queue_t
*q
= bdev_get_queue(dd
->bdev
);
947 if (!q
->issue_flush_fn
)
950 err
= q
->issue_flush_fn(q
, dd
->bdev
->bd_disk
, NULL
);
959 struct mapped_device
*dm_table_get_md(struct dm_table
*t
)
966 EXPORT_SYMBOL(dm_vcalloc
);
967 EXPORT_SYMBOL(dm_get_device
);
968 EXPORT_SYMBOL(dm_put_device
);
969 EXPORT_SYMBOL(dm_table_event
);
970 EXPORT_SYMBOL(dm_table_get_size
);
971 EXPORT_SYMBOL(dm_table_get_mode
);
972 EXPORT_SYMBOL(dm_table_get_md
);
973 EXPORT_SYMBOL(dm_table_put
);
974 EXPORT_SYMBOL(dm_table_get
);
975 EXPORT_SYMBOL(dm_table_unplug_all
);
976 EXPORT_SYMBOL(dm_table_flush_all
);