timerfd: Allow timers to be cancelled when clock was set
[linux-2.6/linux-mips.git] / drivers / mtd / mtdpart.c
blob0a476017478277a925014d36f13ea0ea77c872ee
1 /*
2 * Simple MTD partitioning layer
4 * Copyright © 2000 Nicolas Pitre <nico@fluxnic.net>
5 * Copyright © 2002 Thomas Gleixner <gleixner@linutronix.de>
6 * Copyright © 2000-2010 David Woodhouse <dwmw2@infradead.org>
8 * This program is free software; you can redistribute it and/or modify
9 * it under the terms of the GNU General Public License as published by
10 * the Free Software Foundation; either version 2 of the License, or
11 * (at your option) any later version.
13 * This program is distributed in the hope that it will be useful,
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 * GNU General Public License for more details.
18 * You should have received a copy of the GNU General Public License
19 * along with this program; if not, write to the Free Software
20 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
24 #include <linux/module.h>
25 #include <linux/types.h>
26 #include <linux/kernel.h>
27 #include <linux/slab.h>
28 #include <linux/list.h>
29 #include <linux/kmod.h>
30 #include <linux/mtd/mtd.h>
31 #include <linux/mtd/partitions.h>
32 #include <linux/err.h>
34 /* Our partition linked list */
35 static LIST_HEAD(mtd_partitions);
36 static DEFINE_MUTEX(mtd_partitions_mutex);
38 /* Our partition node structure */
39 struct mtd_part {
40 struct mtd_info mtd;
41 struct mtd_info *master;
42 uint64_t offset;
43 struct list_head list;
47 * Given a pointer to the MTD object in the mtd_part structure, we can retrieve
48 * the pointer to that structure with this macro.
50 #define PART(x) ((struct mtd_part *)(x))
54 * MTD methods which simply translate the effective address and pass through
55 * to the _real_ device.
58 static int part_read(struct mtd_info *mtd, loff_t from, size_t len,
59 size_t *retlen, u_char *buf)
61 struct mtd_part *part = PART(mtd);
62 struct mtd_ecc_stats stats;
63 int res;
65 stats = part->master->ecc_stats;
67 if (from >= mtd->size)
68 len = 0;
69 else if (from + len > mtd->size)
70 len = mtd->size - from;
71 res = part->master->read(part->master, from + part->offset,
72 len, retlen, buf);
73 if (unlikely(res)) {
74 if (res == -EUCLEAN)
75 mtd->ecc_stats.corrected += part->master->ecc_stats.corrected - stats.corrected;
76 if (res == -EBADMSG)
77 mtd->ecc_stats.failed += part->master->ecc_stats.failed - stats.failed;
79 return res;
82 static int part_point(struct mtd_info *mtd, loff_t from, size_t len,
83 size_t *retlen, void **virt, resource_size_t *phys)
85 struct mtd_part *part = PART(mtd);
86 if (from >= mtd->size)
87 len = 0;
88 else if (from + len > mtd->size)
89 len = mtd->size - from;
90 return part->master->point (part->master, from + part->offset,
91 len, retlen, virt, phys);
94 static void part_unpoint(struct mtd_info *mtd, loff_t from, size_t len)
96 struct mtd_part *part = PART(mtd);
98 part->master->unpoint(part->master, from + part->offset, len);
101 static unsigned long part_get_unmapped_area(struct mtd_info *mtd,
102 unsigned long len,
103 unsigned long offset,
104 unsigned long flags)
106 struct mtd_part *part = PART(mtd);
108 offset += part->offset;
109 return part->master->get_unmapped_area(part->master, len, offset,
110 flags);
113 static int part_read_oob(struct mtd_info *mtd, loff_t from,
114 struct mtd_oob_ops *ops)
116 struct mtd_part *part = PART(mtd);
117 int res;
119 if (from >= mtd->size)
120 return -EINVAL;
121 if (ops->datbuf && from + ops->len > mtd->size)
122 return -EINVAL;
125 * If OOB is also requested, make sure that we do not read past the end
126 * of this partition.
128 if (ops->oobbuf) {
129 size_t len, pages;
131 if (ops->mode == MTD_OOB_AUTO)
132 len = mtd->oobavail;
133 else
134 len = mtd->oobsize;
135 pages = mtd_div_by_ws(mtd->size, mtd);
136 pages -= mtd_div_by_ws(from, mtd);
137 if (ops->ooboffs + ops->ooblen > pages * len)
138 return -EINVAL;
141 res = part->master->read_oob(part->master, from + part->offset, ops);
142 if (unlikely(res)) {
143 if (res == -EUCLEAN)
144 mtd->ecc_stats.corrected++;
145 if (res == -EBADMSG)
146 mtd->ecc_stats.failed++;
148 return res;
151 static int part_read_user_prot_reg(struct mtd_info *mtd, loff_t from,
152 size_t len, size_t *retlen, u_char *buf)
154 struct mtd_part *part = PART(mtd);
155 return part->master->read_user_prot_reg(part->master, from,
156 len, retlen, buf);
159 static int part_get_user_prot_info(struct mtd_info *mtd,
160 struct otp_info *buf, size_t len)
162 struct mtd_part *part = PART(mtd);
163 return part->master->get_user_prot_info(part->master, buf, len);
166 static int part_read_fact_prot_reg(struct mtd_info *mtd, loff_t from,
167 size_t len, size_t *retlen, u_char *buf)
169 struct mtd_part *part = PART(mtd);
170 return part->master->read_fact_prot_reg(part->master, from,
171 len, retlen, buf);
174 static int part_get_fact_prot_info(struct mtd_info *mtd, struct otp_info *buf,
175 size_t len)
177 struct mtd_part *part = PART(mtd);
178 return part->master->get_fact_prot_info(part->master, buf, len);
181 static int part_write(struct mtd_info *mtd, loff_t to, size_t len,
182 size_t *retlen, const u_char *buf)
184 struct mtd_part *part = PART(mtd);
185 if (!(mtd->flags & MTD_WRITEABLE))
186 return -EROFS;
187 if (to >= mtd->size)
188 len = 0;
189 else if (to + len > mtd->size)
190 len = mtd->size - to;
191 return part->master->write(part->master, to + part->offset,
192 len, retlen, buf);
195 static int part_panic_write(struct mtd_info *mtd, loff_t to, size_t len,
196 size_t *retlen, const u_char *buf)
198 struct mtd_part *part = PART(mtd);
199 if (!(mtd->flags & MTD_WRITEABLE))
200 return -EROFS;
201 if (to >= mtd->size)
202 len = 0;
203 else if (to + len > mtd->size)
204 len = mtd->size - to;
205 return part->master->panic_write(part->master, to + part->offset,
206 len, retlen, buf);
209 static int part_write_oob(struct mtd_info *mtd, loff_t to,
210 struct mtd_oob_ops *ops)
212 struct mtd_part *part = PART(mtd);
214 if (!(mtd->flags & MTD_WRITEABLE))
215 return -EROFS;
217 if (to >= mtd->size)
218 return -EINVAL;
219 if (ops->datbuf && to + ops->len > mtd->size)
220 return -EINVAL;
221 return part->master->write_oob(part->master, to + part->offset, ops);
224 static int part_write_user_prot_reg(struct mtd_info *mtd, loff_t from,
225 size_t len, size_t *retlen, u_char *buf)
227 struct mtd_part *part = PART(mtd);
228 return part->master->write_user_prot_reg(part->master, from,
229 len, retlen, buf);
232 static int part_lock_user_prot_reg(struct mtd_info *mtd, loff_t from,
233 size_t len)
235 struct mtd_part *part = PART(mtd);
236 return part->master->lock_user_prot_reg(part->master, from, len);
239 static int part_writev(struct mtd_info *mtd, const struct kvec *vecs,
240 unsigned long count, loff_t to, size_t *retlen)
242 struct mtd_part *part = PART(mtd);
243 if (!(mtd->flags & MTD_WRITEABLE))
244 return -EROFS;
245 return part->master->writev(part->master, vecs, count,
246 to + part->offset, retlen);
249 static int part_erase(struct mtd_info *mtd, struct erase_info *instr)
251 struct mtd_part *part = PART(mtd);
252 int ret;
253 if (!(mtd->flags & MTD_WRITEABLE))
254 return -EROFS;
255 if (instr->addr >= mtd->size)
256 return -EINVAL;
257 instr->addr += part->offset;
258 ret = part->master->erase(part->master, instr);
259 if (ret) {
260 if (instr->fail_addr != MTD_FAIL_ADDR_UNKNOWN)
261 instr->fail_addr -= part->offset;
262 instr->addr -= part->offset;
264 return ret;
267 void mtd_erase_callback(struct erase_info *instr)
269 if (instr->mtd->erase == part_erase) {
270 struct mtd_part *part = PART(instr->mtd);
272 if (instr->fail_addr != MTD_FAIL_ADDR_UNKNOWN)
273 instr->fail_addr -= part->offset;
274 instr->addr -= part->offset;
276 if (instr->callback)
277 instr->callback(instr);
279 EXPORT_SYMBOL_GPL(mtd_erase_callback);
281 static int part_lock(struct mtd_info *mtd, loff_t ofs, uint64_t len)
283 struct mtd_part *part = PART(mtd);
284 if ((len + ofs) > mtd->size)
285 return -EINVAL;
286 return part->master->lock(part->master, ofs + part->offset, len);
289 static int part_unlock(struct mtd_info *mtd, loff_t ofs, uint64_t len)
291 struct mtd_part *part = PART(mtd);
292 if ((len + ofs) > mtd->size)
293 return -EINVAL;
294 return part->master->unlock(part->master, ofs + part->offset, len);
297 static int part_is_locked(struct mtd_info *mtd, loff_t ofs, uint64_t len)
299 struct mtd_part *part = PART(mtd);
300 if ((len + ofs) > mtd->size)
301 return -EINVAL;
302 return part->master->is_locked(part->master, ofs + part->offset, len);
305 static void part_sync(struct mtd_info *mtd)
307 struct mtd_part *part = PART(mtd);
308 part->master->sync(part->master);
311 static int part_suspend(struct mtd_info *mtd)
313 struct mtd_part *part = PART(mtd);
314 return part->master->suspend(part->master);
317 static void part_resume(struct mtd_info *mtd)
319 struct mtd_part *part = PART(mtd);
320 part->master->resume(part->master);
323 static int part_block_isbad(struct mtd_info *mtd, loff_t ofs)
325 struct mtd_part *part = PART(mtd);
326 if (ofs >= mtd->size)
327 return -EINVAL;
328 ofs += part->offset;
329 return part->master->block_isbad(part->master, ofs);
332 static int part_block_markbad(struct mtd_info *mtd, loff_t ofs)
334 struct mtd_part *part = PART(mtd);
335 int res;
337 if (!(mtd->flags & MTD_WRITEABLE))
338 return -EROFS;
339 if (ofs >= mtd->size)
340 return -EINVAL;
341 ofs += part->offset;
342 res = part->master->block_markbad(part->master, ofs);
343 if (!res)
344 mtd->ecc_stats.badblocks++;
345 return res;
348 static inline void free_partition(struct mtd_part *p)
350 kfree(p->mtd.name);
351 kfree(p);
355 * This function unregisters and destroy all slave MTD objects which are
356 * attached to the given master MTD object.
359 int del_mtd_partitions(struct mtd_info *master)
361 struct mtd_part *slave, *next;
362 int ret, err = 0;
364 mutex_lock(&mtd_partitions_mutex);
365 list_for_each_entry_safe(slave, next, &mtd_partitions, list)
366 if (slave->master == master) {
367 ret = del_mtd_device(&slave->mtd);
368 if (ret < 0) {
369 err = ret;
370 continue;
372 list_del(&slave->list);
373 free_partition(slave);
375 mutex_unlock(&mtd_partitions_mutex);
377 return err;
379 EXPORT_SYMBOL(del_mtd_partitions);
381 static struct mtd_part *allocate_partition(struct mtd_info *master,
382 const struct mtd_partition *part, int partno,
383 uint64_t cur_offset)
385 struct mtd_part *slave;
386 char *name;
388 /* allocate the partition structure */
389 slave = kzalloc(sizeof(*slave), GFP_KERNEL);
390 name = kstrdup(part->name, GFP_KERNEL);
391 if (!name || !slave) {
392 printk(KERN_ERR"memory allocation error while creating partitions for \"%s\"\n",
393 master->name);
394 kfree(name);
395 kfree(slave);
396 return ERR_PTR(-ENOMEM);
399 /* set up the MTD object for this partition */
400 slave->mtd.type = master->type;
401 slave->mtd.flags = master->flags & ~part->mask_flags;
402 slave->mtd.size = part->size;
403 slave->mtd.writesize = master->writesize;
404 slave->mtd.writebufsize = master->writebufsize;
405 slave->mtd.oobsize = master->oobsize;
406 slave->mtd.oobavail = master->oobavail;
407 slave->mtd.subpage_sft = master->subpage_sft;
409 slave->mtd.name = name;
410 slave->mtd.owner = master->owner;
411 slave->mtd.backing_dev_info = master->backing_dev_info;
413 /* NOTE: we don't arrange MTDs as a tree; it'd be error-prone
414 * to have the same data be in two different partitions.
416 slave->mtd.dev.parent = master->dev.parent;
418 slave->mtd.read = part_read;
419 slave->mtd.write = part_write;
421 if (master->panic_write)
422 slave->mtd.panic_write = part_panic_write;
424 if (master->point && master->unpoint) {
425 slave->mtd.point = part_point;
426 slave->mtd.unpoint = part_unpoint;
429 if (master->get_unmapped_area)
430 slave->mtd.get_unmapped_area = part_get_unmapped_area;
431 if (master->read_oob)
432 slave->mtd.read_oob = part_read_oob;
433 if (master->write_oob)
434 slave->mtd.write_oob = part_write_oob;
435 if (master->read_user_prot_reg)
436 slave->mtd.read_user_prot_reg = part_read_user_prot_reg;
437 if (master->read_fact_prot_reg)
438 slave->mtd.read_fact_prot_reg = part_read_fact_prot_reg;
439 if (master->write_user_prot_reg)
440 slave->mtd.write_user_prot_reg = part_write_user_prot_reg;
441 if (master->lock_user_prot_reg)
442 slave->mtd.lock_user_prot_reg = part_lock_user_prot_reg;
443 if (master->get_user_prot_info)
444 slave->mtd.get_user_prot_info = part_get_user_prot_info;
445 if (master->get_fact_prot_info)
446 slave->mtd.get_fact_prot_info = part_get_fact_prot_info;
447 if (master->sync)
448 slave->mtd.sync = part_sync;
449 if (!partno && !master->dev.class && master->suspend && master->resume) {
450 slave->mtd.suspend = part_suspend;
451 slave->mtd.resume = part_resume;
453 if (master->writev)
454 slave->mtd.writev = part_writev;
455 if (master->lock)
456 slave->mtd.lock = part_lock;
457 if (master->unlock)
458 slave->mtd.unlock = part_unlock;
459 if (master->is_locked)
460 slave->mtd.is_locked = part_is_locked;
461 if (master->block_isbad)
462 slave->mtd.block_isbad = part_block_isbad;
463 if (master->block_markbad)
464 slave->mtd.block_markbad = part_block_markbad;
465 slave->mtd.erase = part_erase;
466 slave->master = master;
467 slave->offset = part->offset;
469 if (slave->offset == MTDPART_OFS_APPEND)
470 slave->offset = cur_offset;
471 if (slave->offset == MTDPART_OFS_NXTBLK) {
472 slave->offset = cur_offset;
473 if (mtd_mod_by_eb(cur_offset, master) != 0) {
474 /* Round up to next erasesize */
475 slave->offset = (mtd_div_by_eb(cur_offset, master) + 1) * master->erasesize;
476 printk(KERN_NOTICE "Moving partition %d: "
477 "0x%012llx -> 0x%012llx\n", partno,
478 (unsigned long long)cur_offset, (unsigned long long)slave->offset);
481 if (slave->mtd.size == MTDPART_SIZ_FULL)
482 slave->mtd.size = master->size - slave->offset;
484 printk(KERN_NOTICE "0x%012llx-0x%012llx : \"%s\"\n", (unsigned long long)slave->offset,
485 (unsigned long long)(slave->offset + slave->mtd.size), slave->mtd.name);
487 /* let's do some sanity checks */
488 if (slave->offset >= master->size) {
489 /* let's register it anyway to preserve ordering */
490 slave->offset = 0;
491 slave->mtd.size = 0;
492 printk(KERN_ERR"mtd: partition \"%s\" is out of reach -- disabled\n",
493 part->name);
494 goto out_register;
496 if (slave->offset + slave->mtd.size > master->size) {
497 slave->mtd.size = master->size - slave->offset;
498 printk(KERN_WARNING"mtd: partition \"%s\" extends beyond the end of device \"%s\" -- size truncated to %#llx\n",
499 part->name, master->name, (unsigned long long)slave->mtd.size);
501 if (master->numeraseregions > 1) {
502 /* Deal with variable erase size stuff */
503 int i, max = master->numeraseregions;
504 u64 end = slave->offset + slave->mtd.size;
505 struct mtd_erase_region_info *regions = master->eraseregions;
507 /* Find the first erase regions which is part of this
508 * partition. */
509 for (i = 0; i < max && regions[i].offset <= slave->offset; i++)
511 /* The loop searched for the region _behind_ the first one */
512 if (i > 0)
513 i--;
515 /* Pick biggest erasesize */
516 for (; i < max && regions[i].offset < end; i++) {
517 if (slave->mtd.erasesize < regions[i].erasesize) {
518 slave->mtd.erasesize = regions[i].erasesize;
521 BUG_ON(slave->mtd.erasesize == 0);
522 } else {
523 /* Single erase size */
524 slave->mtd.erasesize = master->erasesize;
527 if ((slave->mtd.flags & MTD_WRITEABLE) &&
528 mtd_mod_by_eb(slave->offset, &slave->mtd)) {
529 /* Doesn't start on a boundary of major erase size */
530 /* FIXME: Let it be writable if it is on a boundary of
531 * _minor_ erase size though */
532 slave->mtd.flags &= ~MTD_WRITEABLE;
533 printk(KERN_WARNING"mtd: partition \"%s\" doesn't start on an erase block boundary -- force read-only\n",
534 part->name);
536 if ((slave->mtd.flags & MTD_WRITEABLE) &&
537 mtd_mod_by_eb(slave->mtd.size, &slave->mtd)) {
538 slave->mtd.flags &= ~MTD_WRITEABLE;
539 printk(KERN_WARNING"mtd: partition \"%s\" doesn't end on an erase block -- force read-only\n",
540 part->name);
543 slave->mtd.ecclayout = master->ecclayout;
544 if (master->block_isbad) {
545 uint64_t offs = 0;
547 while (offs < slave->mtd.size) {
548 if (master->block_isbad(master,
549 offs + slave->offset))
550 slave->mtd.ecc_stats.badblocks++;
551 offs += slave->mtd.erasesize;
555 out_register:
556 return slave;
559 int mtd_add_partition(struct mtd_info *master, char *name,
560 long long offset, long long length)
562 struct mtd_partition part;
563 struct mtd_part *p, *new;
564 uint64_t start, end;
565 int ret = 0;
567 /* the direct offset is expected */
568 if (offset == MTDPART_OFS_APPEND ||
569 offset == MTDPART_OFS_NXTBLK)
570 return -EINVAL;
572 if (length == MTDPART_SIZ_FULL)
573 length = master->size - offset;
575 if (length <= 0)
576 return -EINVAL;
578 part.name = name;
579 part.size = length;
580 part.offset = offset;
581 part.mask_flags = 0;
582 part.ecclayout = NULL;
584 new = allocate_partition(master, &part, -1, offset);
585 if (IS_ERR(new))
586 return PTR_ERR(new);
588 start = offset;
589 end = offset + length;
591 mutex_lock(&mtd_partitions_mutex);
592 list_for_each_entry(p, &mtd_partitions, list)
593 if (p->master == master) {
594 if ((start >= p->offset) &&
595 (start < (p->offset + p->mtd.size)))
596 goto err_inv;
598 if ((end >= p->offset) &&
599 (end < (p->offset + p->mtd.size)))
600 goto err_inv;
603 list_add(&new->list, &mtd_partitions);
604 mutex_unlock(&mtd_partitions_mutex);
606 add_mtd_device(&new->mtd);
608 return ret;
609 err_inv:
610 mutex_unlock(&mtd_partitions_mutex);
611 free_partition(new);
612 return -EINVAL;
614 EXPORT_SYMBOL_GPL(mtd_add_partition);
616 int mtd_del_partition(struct mtd_info *master, int partno)
618 struct mtd_part *slave, *next;
619 int ret = -EINVAL;
621 mutex_lock(&mtd_partitions_mutex);
622 list_for_each_entry_safe(slave, next, &mtd_partitions, list)
623 if ((slave->master == master) &&
624 (slave->mtd.index == partno)) {
625 ret = del_mtd_device(&slave->mtd);
626 if (ret < 0)
627 break;
629 list_del(&slave->list);
630 free_partition(slave);
631 break;
633 mutex_unlock(&mtd_partitions_mutex);
635 return ret;
637 EXPORT_SYMBOL_GPL(mtd_del_partition);
640 * This function, given a master MTD object and a partition table, creates
641 * and registers slave MTD objects which are bound to the master according to
642 * the partition definitions.
644 * We don't register the master, or expect the caller to have done so,
645 * for reasons of data integrity.
648 int add_mtd_partitions(struct mtd_info *master,
649 const struct mtd_partition *parts,
650 int nbparts)
652 struct mtd_part *slave;
653 uint64_t cur_offset = 0;
654 int i;
656 printk(KERN_NOTICE "Creating %d MTD partitions on \"%s\":\n", nbparts, master->name);
658 for (i = 0; i < nbparts; i++) {
659 slave = allocate_partition(master, parts + i, i, cur_offset);
660 if (IS_ERR(slave))
661 return PTR_ERR(slave);
663 mutex_lock(&mtd_partitions_mutex);
664 list_add(&slave->list, &mtd_partitions);
665 mutex_unlock(&mtd_partitions_mutex);
667 add_mtd_device(&slave->mtd);
669 cur_offset = slave->offset + slave->mtd.size;
672 return 0;
674 EXPORT_SYMBOL(add_mtd_partitions);
676 static DEFINE_SPINLOCK(part_parser_lock);
677 static LIST_HEAD(part_parsers);
679 static struct mtd_part_parser *get_partition_parser(const char *name)
681 struct mtd_part_parser *p, *ret = NULL;
683 spin_lock(&part_parser_lock);
685 list_for_each_entry(p, &part_parsers, list)
686 if (!strcmp(p->name, name) && try_module_get(p->owner)) {
687 ret = p;
688 break;
691 spin_unlock(&part_parser_lock);
693 return ret;
696 int register_mtd_parser(struct mtd_part_parser *p)
698 spin_lock(&part_parser_lock);
699 list_add(&p->list, &part_parsers);
700 spin_unlock(&part_parser_lock);
702 return 0;
704 EXPORT_SYMBOL_GPL(register_mtd_parser);
706 int deregister_mtd_parser(struct mtd_part_parser *p)
708 spin_lock(&part_parser_lock);
709 list_del(&p->list);
710 spin_unlock(&part_parser_lock);
711 return 0;
713 EXPORT_SYMBOL_GPL(deregister_mtd_parser);
715 int parse_mtd_partitions(struct mtd_info *master, const char **types,
716 struct mtd_partition **pparts, unsigned long origin)
718 struct mtd_part_parser *parser;
719 int ret = 0;
721 for ( ; ret <= 0 && *types; types++) {
722 parser = get_partition_parser(*types);
723 if (!parser && !request_module("%s", *types))
724 parser = get_partition_parser(*types);
725 if (!parser) {
726 printk(KERN_NOTICE "%s partition parsing not available\n",
727 *types);
728 continue;
730 ret = (*parser->parse_fn)(master, pparts, origin);
731 if (ret > 0) {
732 printk(KERN_NOTICE "%d %s partitions found on MTD device %s\n",
733 ret, parser->name, master->name);
735 put_partition_parser(parser);
737 return ret;
739 EXPORT_SYMBOL_GPL(parse_mtd_partitions);
741 int mtd_is_partition(struct mtd_info *mtd)
743 struct mtd_part *part;
744 int ispart = 0;
746 mutex_lock(&mtd_partitions_mutex);
747 list_for_each_entry(part, &mtd_partitions, list)
748 if (&part->mtd == mtd) {
749 ispart = 1;
750 break;
752 mutex_unlock(&mtd_partitions_mutex);
754 return ispart;
756 EXPORT_SYMBOL_GPL(mtd_is_partition);