xref: /linux/drivers/md/dm-table.c (revision f3d9478b2ce468c3115b02ecae7e975990697f15)
1 /*
2  * Copyright (C) 2001 Sistina Software (UK) Limited.
3  * Copyright (C) 2004 Red Hat, Inc. All rights reserved.
4  *
5  * This file is released under the GPL.
6  */
7 
8 #include "dm.h"
9 
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>
19 
20 #define MAX_DEPTH 16
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)
24 
25 struct dm_table {
26 	struct mapped_device *md;
27 	atomic_t holders;
28 
29 	/* btree table */
30 	unsigned int depth;
31 	unsigned int counts[MAX_DEPTH];	/* in nodes */
32 	sector_t *index[MAX_DEPTH];
33 
34 	unsigned int num_targets;
35 	unsigned int num_allocated;
36 	sector_t *highs;
37 	struct dm_target *targets;
38 
39 	/*
40 	 * Indicates the rw permissions for the new logical
41 	 * device.  This should be a combination of FMODE_READ
42 	 * and FMODE_WRITE.
43 	 */
44 	int mode;
45 
46 	/* a list of devices used by this table */
47 	struct list_head devices;
48 
49 	/*
50 	 * These are optimistic limits taken from all the
51 	 * targets, some targets will need smaller limits.
52 	 */
53 	struct io_restrictions limits;
54 
55 	/* events get handed up using this callback */
56 	void (*event_fn)(void *);
57 	void *event_context;
58 };
59 
60 /*
61  * Similar to ceiling(log_size(n))
62  */
63 static unsigned int int_log(unsigned int n, unsigned int base)
64 {
65 	int result = 0;
66 
67 	while (n > 1) {
68 		n = dm_div_up(n, base);
69 		result++;
70 	}
71 
72 	return result;
73 }
74 
75 /*
76  * Returns the minimum that is _not_ zero, unless both are zero.
77  */
78 #define min_not_zero(l, r) (l == 0) ? r : ((r == 0) ? l : min(l, r))
79 
80 /*
81  * Combine two io_restrictions, always taking the lower value.
82  */
83 static void combine_restrictions_low(struct io_restrictions *lhs,
84 				     struct io_restrictions *rhs)
85 {
86 	lhs->max_sectors =
87 		min_not_zero(lhs->max_sectors, rhs->max_sectors);
88 
89 	lhs->max_phys_segments =
90 		min_not_zero(lhs->max_phys_segments, rhs->max_phys_segments);
91 
92 	lhs->max_hw_segments =
93 		min_not_zero(lhs->max_hw_segments, rhs->max_hw_segments);
94 
95 	lhs->hardsect_size = max(lhs->hardsect_size, rhs->hardsect_size);
96 
97 	lhs->max_segment_size =
98 		min_not_zero(lhs->max_segment_size, rhs->max_segment_size);
99 
100 	lhs->seg_boundary_mask =
101 		min_not_zero(lhs->seg_boundary_mask, rhs->seg_boundary_mask);
102 
103 	lhs->no_cluster |= rhs->no_cluster;
104 }
105 
106 /*
107  * Calculate the index of the child node of the n'th node k'th key.
108  */
109 static inline unsigned int get_child(unsigned int n, unsigned int k)
110 {
111 	return (n * CHILDREN_PER_NODE) + k;
112 }
113 
114 /*
115  * Return the n'th node of level l from table t.
116  */
117 static inline sector_t *get_node(struct dm_table *t,
118 				 unsigned int l, unsigned int n)
119 {
120 	return t->index[l] + (n * KEYS_PER_NODE);
121 }
122 
123 /*
124  * Return the highest key that you could lookup from the n'th
125  * node on level l of the btree.
126  */
127 static sector_t high(struct dm_table *t, unsigned int l, unsigned int n)
128 {
129 	for (; l < t->depth - 1; l++)
130 		n = get_child(n, CHILDREN_PER_NODE - 1);
131 
132 	if (n >= t->counts[l])
133 		return (sector_t) - 1;
134 
135 	return get_node(t, l, n)[KEYS_PER_NODE - 1];
136 }
137 
138 /*
139  * Fills in a level of the btree based on the highs of the level
140  * below it.
141  */
142 static int setup_btree_index(unsigned int l, struct dm_table *t)
143 {
144 	unsigned int n, k;
145 	sector_t *node;
146 
147 	for (n = 0U; n < t->counts[l]; n++) {
148 		node = get_node(t, l, n);
149 
150 		for (k = 0U; k < KEYS_PER_NODE; k++)
151 			node[k] = high(t, l + 1, get_child(n, k));
152 	}
153 
154 	return 0;
155 }
156 
157 void *dm_vcalloc(unsigned long nmemb, unsigned long elem_size)
158 {
159 	unsigned long size;
160 	void *addr;
161 
162 	/*
163 	 * Check that we're not going to overflow.
164 	 */
165 	if (nmemb > (ULONG_MAX / elem_size))
166 		return NULL;
167 
168 	size = nmemb * elem_size;
169 	addr = vmalloc(size);
170 	if (addr)
171 		memset(addr, 0, size);
172 
173 	return addr;
174 }
175 
176 /*
177  * highs, and targets are managed as dynamic arrays during a
178  * table load.
179  */
180 static int alloc_targets(struct dm_table *t, unsigned int num)
181 {
182 	sector_t *n_highs;
183 	struct dm_target *n_targets;
184 	int n = t->num_targets;
185 
186 	/*
187 	 * Allocate both the target array and offset array at once.
188 	 */
189 	n_highs = (sector_t *) dm_vcalloc(num, sizeof(struct dm_target) +
190 					  sizeof(sector_t));
191 	if (!n_highs)
192 		return -ENOMEM;
193 
194 	n_targets = (struct dm_target *) (n_highs + num);
195 
196 	if (n) {
197 		memcpy(n_highs, t->highs, sizeof(*n_highs) * n);
198 		memcpy(n_targets, t->targets, sizeof(*n_targets) * n);
199 	}
200 
201 	memset(n_highs + n, -1, sizeof(*n_highs) * (num - n));
202 	vfree(t->highs);
203 
204 	t->num_allocated = num;
205 	t->highs = n_highs;
206 	t->targets = n_targets;
207 
208 	return 0;
209 }
210 
211 int dm_table_create(struct dm_table **result, int mode,
212 		    unsigned num_targets, struct mapped_device *md)
213 {
214 	struct dm_table *t = kmalloc(sizeof(*t), GFP_KERNEL);
215 
216 	if (!t)
217 		return -ENOMEM;
218 
219 	memset(t, 0, sizeof(*t));
220 	INIT_LIST_HEAD(&t->devices);
221 	atomic_set(&t->holders, 1);
222 
223 	if (!num_targets)
224 		num_targets = KEYS_PER_NODE;
225 
226 	num_targets = dm_round_up(num_targets, KEYS_PER_NODE);
227 
228 	if (alloc_targets(t, num_targets)) {
229 		kfree(t);
230 		t = NULL;
231 		return -ENOMEM;
232 	}
233 
234 	t->mode = mode;
235 	t->md = md;
236 	*result = t;
237 	return 0;
238 }
239 
240 static void free_devices(struct list_head *devices)
241 {
242 	struct list_head *tmp, *next;
243 
244 	for (tmp = devices->next; tmp != devices; tmp = next) {
245 		struct dm_dev *dd = list_entry(tmp, struct dm_dev, list);
246 		next = tmp->next;
247 		kfree(dd);
248 	}
249 }
250 
251 static void table_destroy(struct dm_table *t)
252 {
253 	unsigned int i;
254 
255 	/* free the indexes (see dm_table_complete) */
256 	if (t->depth >= 2)
257 		vfree(t->index[t->depth - 2]);
258 
259 	/* free the targets */
260 	for (i = 0; i < t->num_targets; i++) {
261 		struct dm_target *tgt = t->targets + i;
262 
263 		if (tgt->type->dtr)
264 			tgt->type->dtr(tgt);
265 
266 		dm_put_target_type(tgt->type);
267 	}
268 
269 	vfree(t->highs);
270 
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");
275 
276 		free_devices(&t->devices);
277 	}
278 
279 	kfree(t);
280 }
281 
282 void dm_table_get(struct dm_table *t)
283 {
284 	atomic_inc(&t->holders);
285 }
286 
287 void dm_table_put(struct dm_table *t)
288 {
289 	if (!t)
290 		return;
291 
292 	if (atomic_dec_and_test(&t->holders))
293 		table_destroy(t);
294 }
295 
296 /*
297  * Checks to see if we need to extend highs or targets.
298  */
299 static inline int check_space(struct dm_table *t)
300 {
301 	if (t->num_targets >= t->num_allocated)
302 		return alloc_targets(t, t->num_allocated * 2);
303 
304 	return 0;
305 }
306 
307 /*
308  * Convert a device path to a dev_t.
309  */
310 static int lookup_device(const char *path, dev_t *dev)
311 {
312 	int r;
313 	struct nameidata nd;
314 	struct inode *inode;
315 
316 	if ((r = path_lookup(path, LOOKUP_FOLLOW, &nd)))
317 		return r;
318 
319 	inode = nd.dentry->d_inode;
320 	if (!inode) {
321 		r = -ENOENT;
322 		goto out;
323 	}
324 
325 	if (!S_ISBLK(inode->i_mode)) {
326 		r = -ENOTBLK;
327 		goto out;
328 	}
329 
330 	*dev = inode->i_rdev;
331 
332  out:
333 	path_release(&nd);
334 	return r;
335 }
336 
337 /*
338  * See if we've already got a device in the list.
339  */
340 static struct dm_dev *find_device(struct list_head *l, dev_t dev)
341 {
342 	struct dm_dev *dd;
343 
344 	list_for_each_entry (dd, l, list)
345 		if (dd->bdev->bd_dev == dev)
346 			return dd;
347 
348 	return NULL;
349 }
350 
351 /*
352  * Open a device so we can use it as a map destination.
353  */
354 static int open_dev(struct dm_dev *d, dev_t dev, struct mapped_device *md)
355 {
356 	static char *_claim_ptr = "I belong to device-mapper";
357 	struct block_device *bdev;
358 
359 	int r;
360 
361 	BUG_ON(d->bdev);
362 
363 	bdev = open_by_devnum(dev, d->mode);
364 	if (IS_ERR(bdev))
365 		return PTR_ERR(bdev);
366 	r = bd_claim_by_disk(bdev, _claim_ptr, dm_disk(md));
367 	if (r)
368 		blkdev_put(bdev);
369 	else
370 		d->bdev = bdev;
371 	return r;
372 }
373 
374 /*
375  * Close a device that we've been using.
376  */
377 static void close_dev(struct dm_dev *d, struct mapped_device *md)
378 {
379 	if (!d->bdev)
380 		return;
381 
382 	bd_release_from_disk(d->bdev, dm_disk(md));
383 	blkdev_put(d->bdev);
384 	d->bdev = NULL;
385 }
386 
387 /*
388  * If possible (ie. blk_size[major] is set), this checks an area
389  * of a destination device is valid.
390  */
391 static int check_device_area(struct dm_dev *dd, sector_t start, sector_t len)
392 {
393 	sector_t dev_size;
394 	dev_size = dd->bdev->bd_inode->i_size >> SECTOR_SHIFT;
395 	return ((start < dev_size) && (len <= (dev_size - start)));
396 }
397 
398 /*
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
401  * device.
402  */
403 static int upgrade_mode(struct dm_dev *dd, int new_mode, struct mapped_device *md)
404 {
405 	int r;
406 	struct dm_dev dd_copy;
407 	dev_t dev = dd->bdev->bd_dev;
408 
409 	dd_copy = *dd;
410 
411 	dd->mode |= new_mode;
412 	dd->bdev = NULL;
413 	r = open_dev(dd, dev, md);
414 	if (!r)
415 		close_dev(&dd_copy, md);
416 	else
417 		*dd = dd_copy;
418 
419 	return r;
420 }
421 
422 /*
423  * Add a device to the list, or just increment the usage count if
424  * it's already present.
425  */
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)
429 {
430 	int r;
431 	dev_t dev;
432 	struct dm_dev *dd;
433 	unsigned int major, minor;
434 
435 	BUG_ON(!t);
436 
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)
441 			return -EOVERFLOW;
442 	} else {
443 		/* convert the path to a device */
444 		if ((r = lookup_device(path, &dev)))
445 			return r;
446 	}
447 
448 	dd = find_device(&t->devices, dev);
449 	if (!dd) {
450 		dd = kmalloc(sizeof(*dd), GFP_KERNEL);
451 		if (!dd)
452 			return -ENOMEM;
453 
454 		dd->mode = mode;
455 		dd->bdev = NULL;
456 
457 		if ((r = open_dev(dd, dev, t->md))) {
458 			kfree(dd);
459 			return r;
460 		}
461 
462 		format_dev_t(dd->name, dev);
463 
464 		atomic_set(&dd->count, 0);
465 		list_add(&dd->list, &t->devices);
466 
467 	} else if (dd->mode != (mode | dd->mode)) {
468 		r = upgrade_mode(dd, mode, t->md);
469 		if (r)
470 			return r;
471 	}
472 	atomic_inc(&dd->count);
473 
474 	if (!check_device_area(dd, start, len)) {
475 		DMWARN("device %s too small for target", path);
476 		dm_put_device(ti, dd);
477 		return -EINVAL;
478 	}
479 
480 	*result = dd;
481 
482 	return 0;
483 }
484 
485 
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)
488 {
489 	int r = __table_get_device(ti->table, ti, path,
490 				   start, len, mode, result);
491 	if (!r) {
492 		request_queue_t *q = bdev_get_queue((*result)->bdev);
493 		struct io_restrictions *rs = &ti->limits;
494 
495 		/*
496 		 * Combine the device limits low.
497 		 *
498 		 * FIXME: if we move an io_restriction struct
499 		 *        into q this would just be a call to
500 		 *        combine_restrictions_low()
501 		 */
502 		rs->max_sectors =
503 			min_not_zero(rs->max_sectors, q->max_sectors);
504 
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.
511 		 */
512 		if (q->merge_bvec_fn)
513 			rs->max_sectors =
514 				min_not_zero(rs->max_sectors,
515 					     (unsigned int) (PAGE_SIZE >> 9));
516 
517 		rs->max_phys_segments =
518 			min_not_zero(rs->max_phys_segments,
519 				     q->max_phys_segments);
520 
521 		rs->max_hw_segments =
522 			min_not_zero(rs->max_hw_segments, q->max_hw_segments);
523 
524 		rs->hardsect_size = max(rs->hardsect_size, q->hardsect_size);
525 
526 		rs->max_segment_size =
527 			min_not_zero(rs->max_segment_size, q->max_segment_size);
528 
529 		rs->seg_boundary_mask =
530 			min_not_zero(rs->seg_boundary_mask,
531 				     q->seg_boundary_mask);
532 
533 		rs->no_cluster |= !test_bit(QUEUE_FLAG_CLUSTER, &q->queue_flags);
534 	}
535 
536 	return r;
537 }
538 
539 /*
540  * Decrement a devices use count and remove it if necessary.
541  */
542 void dm_put_device(struct dm_target *ti, struct dm_dev *dd)
543 {
544 	if (atomic_dec_and_test(&dd->count)) {
545 		close_dev(dd, ti->table->md);
546 		list_del(&dd->list);
547 		kfree(dd);
548 	}
549 }
550 
551 /*
552  * Checks to see if the target joins onto the end of the table.
553  */
554 static int adjoin(struct dm_table *table, struct dm_target *ti)
555 {
556 	struct dm_target *prev;
557 
558 	if (!table->num_targets)
559 		return !ti->begin;
560 
561 	prev = &table->targets[table->num_targets - 1];
562 	return (ti->begin == (prev->begin + prev->len));
563 }
564 
565 /*
566  * Used to dynamically allocate the arg array.
567  */
568 static char **realloc_argv(unsigned *array_size, char **old_argv)
569 {
570 	char **argv;
571 	unsigned new_size;
572 
573 	new_size = *array_size ? *array_size * 2 : 64;
574 	argv = kmalloc(new_size * sizeof(*argv), GFP_KERNEL);
575 	if (argv) {
576 		memcpy(argv, old_argv, *array_size * sizeof(*argv));
577 		*array_size = new_size;
578 	}
579 
580 	kfree(old_argv);
581 	return argv;
582 }
583 
584 /*
585  * Destructively splits up the argument list to pass to ctr.
586  */
587 int dm_split_args(int *argc, char ***argvp, char *input)
588 {
589 	char *start, *end = input, *out, **argv = NULL;
590 	unsigned array_size = 0;
591 
592 	*argc = 0;
593 	argv = realloc_argv(&array_size, argv);
594 	if (!argv)
595 		return -ENOMEM;
596 
597 	while (1) {
598 		start = end;
599 
600 		/* Skip whitespace */
601 		while (*start && isspace(*start))
602 			start++;
603 
604 		if (!*start)
605 			break;	/* success, we hit the end */
606 
607 		/* 'out' is used to remove any back-quotes */
608 		end = out = start;
609 		while (*end) {
610 			/* Everything apart from '\0' can be quoted */
611 			if (*end == '\\' && *(end + 1)) {
612 				*out++ = *(end + 1);
613 				end += 2;
614 				continue;
615 			}
616 
617 			if (isspace(*end))
618 				break;	/* end of token */
619 
620 			*out++ = *end++;
621 		}
622 
623 		/* have we already filled the array ? */
624 		if ((*argc + 1) > array_size) {
625 			argv = realloc_argv(&array_size, argv);
626 			if (!argv)
627 				return -ENOMEM;
628 		}
629 
630 		/* we know this is whitespace */
631 		if (*end)
632 			end++;
633 
634 		/* terminate the string and put it in the array */
635 		*out = '\0';
636 		argv[*argc] = start;
637 		(*argc)++;
638 	}
639 
640 	*argvp = argv;
641 	return 0;
642 }
643 
644 static void check_for_valid_limits(struct io_restrictions *rs)
645 {
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;
658 }
659 
660 int dm_table_add_target(struct dm_table *t, const char *type,
661 			sector_t start, sector_t len, char *params)
662 {
663 	int r = -EINVAL, argc;
664 	char **argv;
665 	struct dm_target *tgt;
666 
667 	if ((r = check_space(t)))
668 		return r;
669 
670 	tgt = t->targets + t->num_targets;
671 	memset(tgt, 0, sizeof(*tgt));
672 
673 	if (!len) {
674 		tgt->error = "zero-length target";
675 		DMERR("%s", tgt->error);
676 		return -EINVAL;
677 	}
678 
679 	tgt->type = dm_get_target_type(type);
680 	if (!tgt->type) {
681 		tgt->error = "unknown target type";
682 		DMERR("%s", tgt->error);
683 		return -EINVAL;
684 	}
685 
686 	tgt->table = t;
687 	tgt->begin = start;
688 	tgt->len = len;
689 	tgt->error = "Unknown error";
690 
691 	/*
692 	 * Does this target adjoin the previous one ?
693 	 */
694 	if (!adjoin(t, tgt)) {
695 		tgt->error = "Gap in table";
696 		r = -EINVAL;
697 		goto bad;
698 	}
699 
700 	r = dm_split_args(&argc, &argv, params);
701 	if (r) {
702 		tgt->error = "couldn't split parameters (insufficient memory)";
703 		goto bad;
704 	}
705 
706 	r = tgt->type->ctr(tgt, argc, argv);
707 	kfree(argv);
708 	if (r)
709 		goto bad;
710 
711 	t->highs[t->num_targets++] = tgt->begin + tgt->len - 1;
712 
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);
716 	return 0;
717 
718  bad:
719 	DMERR("%s", tgt->error);
720 	dm_put_target_type(tgt->type);
721 	return r;
722 }
723 
724 static int setup_indexes(struct dm_table *t)
725 {
726 	int i;
727 	unsigned int total = 0;
728 	sector_t *indexes;
729 
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];
734 	}
735 
736 	indexes = (sector_t *) dm_vcalloc(total, (unsigned long) NODE_SIZE);
737 	if (!indexes)
738 		return -ENOMEM;
739 
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);
745 	}
746 
747 	return 0;
748 }
749 
750 /*
751  * Builds the btree to index the map.
752  */
753 int dm_table_complete(struct dm_table *t)
754 {
755 	int r = 0;
756 	unsigned int leaf_nodes;
757 
758 	check_for_valid_limits(&t->limits);
759 
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);
763 
764 	/* leaf layer has already been set up */
765 	t->counts[t->depth - 1] = leaf_nodes;
766 	t->index[t->depth - 1] = t->highs;
767 
768 	if (t->depth >= 2)
769 		r = setup_indexes(t);
770 
771 	return r;
772 }
773 
774 static DEFINE_MUTEX(_event_lock);
775 void dm_table_event_callback(struct dm_table *t,
776 			     void (*fn)(void *), void *context)
777 {
778 	mutex_lock(&_event_lock);
779 	t->event_fn = fn;
780 	t->event_context = context;
781 	mutex_unlock(&_event_lock);
782 }
783 
784 void dm_table_event(struct dm_table *t)
785 {
786 	/*
787 	 * You can no longer call dm_table_event() from interrupt
788 	 * context, use a bottom half instead.
789 	 */
790 	BUG_ON(in_interrupt());
791 
792 	mutex_lock(&_event_lock);
793 	if (t->event_fn)
794 		t->event_fn(t->event_context);
795 	mutex_unlock(&_event_lock);
796 }
797 
798 sector_t dm_table_get_size(struct dm_table *t)
799 {
800 	return t->num_targets ? (t->highs[t->num_targets - 1] + 1) : 0;
801 }
802 
803 struct dm_target *dm_table_get_target(struct dm_table *t, unsigned int index)
804 {
805 	if (index > t->num_targets)
806 		return NULL;
807 
808 	return t->targets + index;
809 }
810 
811 /*
812  * Search the btree for the correct target.
813  */
814 struct dm_target *dm_table_find_target(struct dm_table *t, sector_t sector)
815 {
816 	unsigned int l, n = 0, k = 0;
817 	sector_t *node;
818 
819 	for (l = 0; l < t->depth; l++) {
820 		n = get_child(n, k);
821 		node = get_node(t, l, n);
822 
823 		for (k = 0; k < KEYS_PER_NODE; k++)
824 			if (node[k] >= sector)
825 				break;
826 	}
827 
828 	return &t->targets[(KEYS_PER_NODE * n) + k];
829 }
830 
831 void dm_table_set_restrictions(struct dm_table *t, struct request_queue *q)
832 {
833 	/*
834 	 * Make sure we obey the optimistic sub devices
835 	 * restrictions.
836 	 */
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);
845 	else
846 		q->queue_flags |= (1 << QUEUE_FLAG_CLUSTER);
847 
848 }
849 
850 unsigned int dm_table_get_num_targets(struct dm_table *t)
851 {
852 	return t->num_targets;
853 }
854 
855 struct list_head *dm_table_get_devices(struct dm_table *t)
856 {
857 	return &t->devices;
858 }
859 
860 int dm_table_get_mode(struct dm_table *t)
861 {
862 	return t->mode;
863 }
864 
865 static void suspend_targets(struct dm_table *t, unsigned postsuspend)
866 {
867 	int i = t->num_targets;
868 	struct dm_target *ti = t->targets;
869 
870 	while (i--) {
871 		if (postsuspend) {
872 			if (ti->type->postsuspend)
873 				ti->type->postsuspend(ti);
874 		} else if (ti->type->presuspend)
875 			ti->type->presuspend(ti);
876 
877 		ti++;
878 	}
879 }
880 
881 void dm_table_presuspend_targets(struct dm_table *t)
882 {
883 	if (!t)
884 		return;
885 
886 	return suspend_targets(t, 0);
887 }
888 
889 void dm_table_postsuspend_targets(struct dm_table *t)
890 {
891 	if (!t)
892 		return;
893 
894 	return suspend_targets(t, 1);
895 }
896 
897 void dm_table_resume_targets(struct dm_table *t)
898 {
899 	int i;
900 
901 	for (i = 0; i < t->num_targets; i++) {
902 		struct dm_target *ti = t->targets + i;
903 
904 		if (ti->type->resume)
905 			ti->type->resume(ti);
906 	}
907 }
908 
909 int dm_table_any_congested(struct dm_table *t, int bdi_bits)
910 {
911 	struct list_head *d, *devices;
912 	int r = 0;
913 
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);
919 	}
920 
921 	return r;
922 }
923 
924 void dm_table_unplug_all(struct dm_table *t)
925 {
926 	struct list_head *d, *devices = dm_table_get_devices(t);
927 
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);
931 
932 		if (q->unplug_fn)
933 			q->unplug_fn(q);
934 	}
935 }
936 
937 int dm_table_flush_all(struct dm_table *t)
938 {
939 	struct list_head *d, *devices = dm_table_get_devices(t);
940 	int ret = 0;
941 
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);
945 		int err;
946 
947 		if (!q->issue_flush_fn)
948 			err = -EOPNOTSUPP;
949 		else
950 			err = q->issue_flush_fn(q, dd->bdev->bd_disk, NULL);
951 
952 		if (!ret)
953 			ret = err;
954 	}
955 
956 	return ret;
957 }
958 
959 struct mapped_device *dm_table_get_md(struct dm_table *t)
960 {
961 	dm_get(t->md);
962 
963 	return t->md;
964 }
965 
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);
977