2 * Copyright (C) 2003 Sistina Software Limited.
3 * Copyright (C) 2004-2008 Red Hat, Inc. All rights reserved.
5 * This file is released under the GPL.
8 #include <linux/dm-dirty-log.h>
9 #include <linux/dm-region-hash.h>
11 #include <linux/ctype.h>
12 #include <linux/init.h>
13 #include <linux/module.h>
14 #include <linux/slab.h>
15 #include <linux/vmalloc.h>
19 #define DM_MSG_PREFIX "region hash"
21 /*-----------------------------------------------------------------
24 * The mirror splits itself up into discrete regions. Each
25 * region can be in one of three states: clean, dirty,
26 * nosync. There is no need to put clean regions in the hash.
28 * In addition to being present in the hash table a region _may_
29 * be present on one of three lists.
31 * clean_regions: Regions on this list have no io pending to
32 * them, they are in sync, we are no longer interested in them,
33 * they are dull. dm_rh_update_states() will remove them from the
36 * quiesced_regions: These regions have been spun down, ready
37 * for recovery. rh_recovery_start() will remove regions from
38 * this list and hand them to kmirrord, which will schedule the
39 * recovery io with kcopyd.
41 * recovered_regions: Regions that kcopyd has successfully
42 * recovered. dm_rh_update_states() will now schedule any delayed
43 * io, up the recovery_count, and remove the region from the
47 * A rw spin lock 'hash_lock' protects just the hash table,
48 * this is never held in write mode from interrupt context,
49 * which I believe means that we only have to disable irqs when
52 * An ordinary spin lock 'region_lock' that protects the three
53 * lists in the region_hash, with the 'state', 'list' and
54 * 'delayed_bios' fields of the regions. This is used from irq
55 * context, so all other uses will have to suspend local irqs.
56 *---------------------------------------------------------------*/
57 struct dm_region_hash
{
59 unsigned region_shift
;
61 /* holds persistent region state */
62 struct dm_dirty_log
*log
;
66 mempool_t
*region_pool
;
71 struct list_head
*buckets
;
73 unsigned max_recovery
; /* Max # of regions to recover in parallel */
75 spinlock_t region_lock
;
76 atomic_t recovery_in_flight
;
77 struct semaphore recovery_count
;
78 struct list_head clean_regions
;
79 struct list_head quiesced_regions
;
80 struct list_head recovered_regions
;
81 struct list_head failed_recovered_regions
;
84 * If there was a barrier failure no regions can be marked clean.
89 sector_t target_begin
;
91 /* Callback function to schedule bios writes */
92 void (*dispatch_bios
)(void *context
, struct bio_list
*bios
);
94 /* Callback function to wakeup callers worker thread. */
95 void (*wakeup_workers
)(void *context
);
97 /* Callback function to wakeup callers recovery waiters. */
98 void (*wakeup_all_recovery_waiters
)(void *context
);
102 struct dm_region_hash
*rh
;
106 struct list_head hash_list
;
107 struct list_head list
;
110 struct bio_list delayed_bios
;
116 static region_t
dm_rh_sector_to_region(struct dm_region_hash
*rh
, sector_t sector
)
118 return sector
>> rh
->region_shift
;
121 sector_t
dm_rh_region_to_sector(struct dm_region_hash
*rh
, region_t region
)
123 return region
<< rh
->region_shift
;
125 EXPORT_SYMBOL_GPL(dm_rh_region_to_sector
);
127 region_t
dm_rh_bio_to_region(struct dm_region_hash
*rh
, struct bio
*bio
)
129 return dm_rh_sector_to_region(rh
, bio
->bi_sector
- rh
->target_begin
);
131 EXPORT_SYMBOL_GPL(dm_rh_bio_to_region
);
133 void *dm_rh_region_context(struct dm_region
*reg
)
135 return reg
->rh
->context
;
137 EXPORT_SYMBOL_GPL(dm_rh_region_context
);
139 region_t
dm_rh_get_region_key(struct dm_region
*reg
)
143 EXPORT_SYMBOL_GPL(dm_rh_get_region_key
);
145 sector_t
dm_rh_get_region_size(struct dm_region_hash
*rh
)
147 return rh
->region_size
;
149 EXPORT_SYMBOL_GPL(dm_rh_get_region_size
);
151 #define RH_HASH_MULT 2654435387U
152 #define RH_HASH_SHIFT 12
154 #define MIN_REGIONS 64
155 struct dm_region_hash
*dm_region_hash_create(
156 void *context
, void (*dispatch_bios
)(void *context
,
157 struct bio_list
*bios
),
158 void (*wakeup_workers
)(void *context
),
159 void (*wakeup_all_recovery_waiters
)(void *context
),
160 sector_t target_begin
, unsigned max_recovery
,
161 struct dm_dirty_log
*log
, uint32_t region_size
,
164 struct dm_region_hash
*rh
;
165 unsigned nr_buckets
, max_buckets
;
169 * Calculate a suitable number of buckets for our hash
172 max_buckets
= nr_regions
>> 6;
173 for (nr_buckets
= 128u; nr_buckets
< max_buckets
; nr_buckets
<<= 1)
177 rh
= kmalloc(sizeof(*rh
), GFP_KERNEL
);
179 DMERR("unable to allocate region hash memory");
180 return ERR_PTR(-ENOMEM
);
183 rh
->context
= context
;
184 rh
->dispatch_bios
= dispatch_bios
;
185 rh
->wakeup_workers
= wakeup_workers
;
186 rh
->wakeup_all_recovery_waiters
= wakeup_all_recovery_waiters
;
187 rh
->target_begin
= target_begin
;
188 rh
->max_recovery
= max_recovery
;
190 rh
->region_size
= region_size
;
191 rh
->region_shift
= ffs(region_size
) - 1;
192 rwlock_init(&rh
->hash_lock
);
193 rh
->mask
= nr_buckets
- 1;
194 rh
->nr_buckets
= nr_buckets
;
196 rh
->shift
= RH_HASH_SHIFT
;
197 rh
->prime
= RH_HASH_MULT
;
199 rh
->buckets
= vmalloc(nr_buckets
* sizeof(*rh
->buckets
));
201 DMERR("unable to allocate region hash bucket memory");
203 return ERR_PTR(-ENOMEM
);
206 for (i
= 0; i
< nr_buckets
; i
++)
207 INIT_LIST_HEAD(rh
->buckets
+ i
);
209 spin_lock_init(&rh
->region_lock
);
210 sema_init(&rh
->recovery_count
, 0);
211 atomic_set(&rh
->recovery_in_flight
, 0);
212 INIT_LIST_HEAD(&rh
->clean_regions
);
213 INIT_LIST_HEAD(&rh
->quiesced_regions
);
214 INIT_LIST_HEAD(&rh
->recovered_regions
);
215 INIT_LIST_HEAD(&rh
->failed_recovered_regions
);
216 rh
->barrier_failure
= 0;
218 rh
->region_pool
= mempool_create_kmalloc_pool(MIN_REGIONS
,
219 sizeof(struct dm_region
));
220 if (!rh
->region_pool
) {
223 rh
= ERR_PTR(-ENOMEM
);
228 EXPORT_SYMBOL_GPL(dm_region_hash_create
);
230 void dm_region_hash_destroy(struct dm_region_hash
*rh
)
233 struct dm_region
*reg
, *nreg
;
235 BUG_ON(!list_empty(&rh
->quiesced_regions
));
236 for (h
= 0; h
< rh
->nr_buckets
; h
++) {
237 list_for_each_entry_safe(reg
, nreg
, rh
->buckets
+ h
,
239 BUG_ON(atomic_read(®
->pending
));
240 mempool_free(reg
, rh
->region_pool
);
245 dm_dirty_log_destroy(rh
->log
);
248 mempool_destroy(rh
->region_pool
);
253 EXPORT_SYMBOL_GPL(dm_region_hash_destroy
);
255 struct dm_dirty_log
*dm_rh_dirty_log(struct dm_region_hash
*rh
)
259 EXPORT_SYMBOL_GPL(dm_rh_dirty_log
);
261 static unsigned rh_hash(struct dm_region_hash
*rh
, region_t region
)
263 return (unsigned) ((region
* rh
->prime
) >> rh
->shift
) & rh
->mask
;
266 static struct dm_region
*__rh_lookup(struct dm_region_hash
*rh
, region_t region
)
268 struct dm_region
*reg
;
269 struct list_head
*bucket
= rh
->buckets
+ rh_hash(rh
, region
);
271 list_for_each_entry(reg
, bucket
, hash_list
)
272 if (reg
->key
== region
)
278 static void __rh_insert(struct dm_region_hash
*rh
, struct dm_region
*reg
)
280 list_add(®
->hash_list
, rh
->buckets
+ rh_hash(rh
, reg
->key
));
283 static struct dm_region
*__rh_alloc(struct dm_region_hash
*rh
, region_t region
)
285 struct dm_region
*reg
, *nreg
;
287 nreg
= mempool_alloc(rh
->region_pool
, GFP_ATOMIC
);
289 nreg
= kmalloc(sizeof(*nreg
), GFP_NOIO
| __GFP_NOFAIL
);
291 nreg
->state
= rh
->log
->type
->in_sync(rh
->log
, region
, 1) ?
292 DM_RH_CLEAN
: DM_RH_NOSYNC
;
295 INIT_LIST_HEAD(&nreg
->list
);
296 atomic_set(&nreg
->pending
, 0);
297 bio_list_init(&nreg
->delayed_bios
);
299 write_lock_irq(&rh
->hash_lock
);
300 reg
= __rh_lookup(rh
, region
);
302 /* We lost the race. */
303 mempool_free(nreg
, rh
->region_pool
);
305 __rh_insert(rh
, nreg
);
306 if (nreg
->state
== DM_RH_CLEAN
) {
307 spin_lock(&rh
->region_lock
);
308 list_add(&nreg
->list
, &rh
->clean_regions
);
309 spin_unlock(&rh
->region_lock
);
314 write_unlock_irq(&rh
->hash_lock
);
319 static struct dm_region
*__rh_find(struct dm_region_hash
*rh
, region_t region
)
321 struct dm_region
*reg
;
323 reg
= __rh_lookup(rh
, region
);
325 read_unlock(&rh
->hash_lock
);
326 reg
= __rh_alloc(rh
, region
);
327 read_lock(&rh
->hash_lock
);
333 int dm_rh_get_state(struct dm_region_hash
*rh
, region_t region
, int may_block
)
336 struct dm_region
*reg
;
338 read_lock(&rh
->hash_lock
);
339 reg
= __rh_lookup(rh
, region
);
340 read_unlock(&rh
->hash_lock
);
346 * The region wasn't in the hash, so we fall back to the
349 r
= rh
->log
->type
->in_sync(rh
->log
, region
, may_block
);
352 * Any error from the dirty log (eg. -EWOULDBLOCK) gets
353 * taken as a DM_RH_NOSYNC
355 return r
== 1 ? DM_RH_CLEAN
: DM_RH_NOSYNC
;
357 EXPORT_SYMBOL_GPL(dm_rh_get_state
);
359 static void complete_resync_work(struct dm_region
*reg
, int success
)
361 struct dm_region_hash
*rh
= reg
->rh
;
363 rh
->log
->type
->set_region_sync(rh
->log
, reg
->key
, success
);
366 * Dispatch the bios before we call 'wake_up_all'.
367 * This is important because if we are suspending,
368 * we want to know that recovery is complete and
369 * the work queue is flushed. If we wake_up_all
370 * before we dispatch_bios (queue bios and call wake()),
371 * then we risk suspending before the work queue
372 * has been properly flushed.
374 rh
->dispatch_bios(rh
->context
, ®
->delayed_bios
);
375 if (atomic_dec_and_test(&rh
->recovery_in_flight
))
376 rh
->wakeup_all_recovery_waiters(rh
->context
);
377 up(&rh
->recovery_count
);
384 * The bio was written on some mirror(s) but failed on other mirror(s).
385 * We can successfully endio the bio but should avoid the region being
386 * marked clean by setting the state DM_RH_NOSYNC.
388 * This function is _not_ safe in interrupt context!
390 void dm_rh_mark_nosync(struct dm_region_hash
*rh
, struct bio
*bio
)
393 struct dm_dirty_log
*log
= rh
->log
;
394 struct dm_region
*reg
;
395 region_t region
= dm_rh_bio_to_region(rh
, bio
);
398 if (bio_empty_barrier(bio
)) {
399 rh
->barrier_failure
= 1;
403 /* We must inform the log that the sync count has changed. */
404 log
->type
->set_region_sync(log
, region
, 0);
406 read_lock(&rh
->hash_lock
);
407 reg
= __rh_find(rh
, region
);
408 read_unlock(&rh
->hash_lock
);
410 /* region hash entry should exist because write was in-flight */
412 BUG_ON(!list_empty(®
->list
));
414 spin_lock_irqsave(&rh
->region_lock
, flags
);
418 * 2) DM_RH_NOSYNC: was dirty, other preceeding writes failed
419 * 3) DM_RH_RECOVERING: flushing pending writes
420 * Either case, the region should have not been connected to list.
422 recovering
= (reg
->state
== DM_RH_RECOVERING
);
423 reg
->state
= DM_RH_NOSYNC
;
424 BUG_ON(!list_empty(®
->list
));
425 spin_unlock_irqrestore(&rh
->region_lock
, flags
);
428 complete_resync_work(reg
, 0);
430 EXPORT_SYMBOL_GPL(dm_rh_mark_nosync
);
432 void dm_rh_update_states(struct dm_region_hash
*rh
, int errors_handled
)
434 struct dm_region
*reg
, *next
;
437 LIST_HEAD(recovered
);
438 LIST_HEAD(failed_recovered
);
441 * Quickly grab the lists.
443 write_lock_irq(&rh
->hash_lock
);
444 spin_lock(&rh
->region_lock
);
445 if (!list_empty(&rh
->clean_regions
)) {
446 list_splice_init(&rh
->clean_regions
, &clean
);
448 list_for_each_entry(reg
, &clean
, list
)
449 list_del(®
->hash_list
);
452 if (!list_empty(&rh
->recovered_regions
)) {
453 list_splice_init(&rh
->recovered_regions
, &recovered
);
455 list_for_each_entry(reg
, &recovered
, list
)
456 list_del(®
->hash_list
);
459 if (!list_empty(&rh
->failed_recovered_regions
)) {
460 list_splice_init(&rh
->failed_recovered_regions
,
463 list_for_each_entry(reg
, &failed_recovered
, list
)
464 list_del(®
->hash_list
);
467 spin_unlock(&rh
->region_lock
);
468 write_unlock_irq(&rh
->hash_lock
);
471 * All the regions on the recovered and clean lists have
472 * now been pulled out of the system, so no need to do
475 list_for_each_entry_safe(reg
, next
, &recovered
, list
) {
476 rh
->log
->type
->clear_region(rh
->log
, reg
->key
);
477 complete_resync_work(reg
, 1);
478 mempool_free(reg
, rh
->region_pool
);
481 list_for_each_entry_safe(reg
, next
, &failed_recovered
, list
) {
482 complete_resync_work(reg
, errors_handled
? 0 : 1);
483 mempool_free(reg
, rh
->region_pool
);
486 list_for_each_entry_safe(reg
, next
, &clean
, list
) {
487 rh
->log
->type
->clear_region(rh
->log
, reg
->key
);
488 mempool_free(reg
, rh
->region_pool
);
491 rh
->log
->type
->flush(rh
->log
);
493 EXPORT_SYMBOL_GPL(dm_rh_update_states
);
495 static void rh_inc(struct dm_region_hash
*rh
, region_t region
)
497 struct dm_region
*reg
;
499 read_lock(&rh
->hash_lock
);
500 reg
= __rh_find(rh
, region
);
502 spin_lock_irq(&rh
->region_lock
);
503 atomic_inc(®
->pending
);
505 if (reg
->state
== DM_RH_CLEAN
) {
506 reg
->state
= DM_RH_DIRTY
;
507 list_del_init(®
->list
); /* take off the clean list */
508 spin_unlock_irq(&rh
->region_lock
);
510 rh
->log
->type
->mark_region(rh
->log
, reg
->key
);
512 spin_unlock_irq(&rh
->region_lock
);
515 read_unlock(&rh
->hash_lock
);
518 void dm_rh_inc_pending(struct dm_region_hash
*rh
, struct bio_list
*bios
)
522 for (bio
= bios
->head
; bio
; bio
= bio
->bi_next
) {
523 if (bio_empty_barrier(bio
))
525 rh_inc(rh
, dm_rh_bio_to_region(rh
, bio
));
528 EXPORT_SYMBOL_GPL(dm_rh_inc_pending
);
530 void dm_rh_dec(struct dm_region_hash
*rh
, region_t region
)
533 struct dm_region
*reg
;
536 read_lock(&rh
->hash_lock
);
537 reg
= __rh_lookup(rh
, region
);
538 read_unlock(&rh
->hash_lock
);
540 spin_lock_irqsave(&rh
->region_lock
, flags
);
541 if (atomic_dec_and_test(®
->pending
)) {
543 * There is no pending I/O for this region.
544 * We can move the region to corresponding list for next action.
545 * At this point, the region is not yet connected to any list.
547 * If the state is DM_RH_NOSYNC, the region should be kept off
549 * The hash entry for DM_RH_NOSYNC will remain in memory
550 * until the region is recovered or the map is reloaded.
553 /* do nothing for DM_RH_NOSYNC */
554 if (unlikely(rh
->barrier_failure
)) {
556 * If a write barrier failed some time ago, we
557 * don't know whether or not this write made it
558 * to the disk, so we must resync the device.
560 reg
->state
= DM_RH_NOSYNC
;
561 } else if (reg
->state
== DM_RH_RECOVERING
) {
562 list_add_tail(®
->list
, &rh
->quiesced_regions
);
563 } else if (reg
->state
== DM_RH_DIRTY
) {
564 reg
->state
= DM_RH_CLEAN
;
565 list_add(®
->list
, &rh
->clean_regions
);
569 spin_unlock_irqrestore(&rh
->region_lock
, flags
);
572 rh
->wakeup_workers(rh
->context
);
574 EXPORT_SYMBOL_GPL(dm_rh_dec
);
577 * Starts quiescing a region in preparation for recovery.
579 static int __rh_recovery_prepare(struct dm_region_hash
*rh
)
583 struct dm_region
*reg
;
586 * Ask the dirty log what's next.
588 r
= rh
->log
->type
->get_resync_work(rh
->log
, ®ion
);
593 * Get this region, and start it quiescing by setting the
596 read_lock(&rh
->hash_lock
);
597 reg
= __rh_find(rh
, region
);
598 read_unlock(&rh
->hash_lock
);
600 spin_lock_irq(&rh
->region_lock
);
601 reg
->state
= DM_RH_RECOVERING
;
603 /* Already quiesced ? */
604 if (atomic_read(®
->pending
))
605 list_del_init(®
->list
);
607 list_move(®
->list
, &rh
->quiesced_regions
);
609 spin_unlock_irq(&rh
->region_lock
);
614 void dm_rh_recovery_prepare(struct dm_region_hash
*rh
)
616 /* Extra reference to avoid race with dm_rh_stop_recovery */
617 atomic_inc(&rh
->recovery_in_flight
);
619 while (!down_trylock(&rh
->recovery_count
)) {
620 atomic_inc(&rh
->recovery_in_flight
);
621 if (__rh_recovery_prepare(rh
) <= 0) {
622 atomic_dec(&rh
->recovery_in_flight
);
623 up(&rh
->recovery_count
);
628 /* Drop the extra reference */
629 if (atomic_dec_and_test(&rh
->recovery_in_flight
))
630 rh
->wakeup_all_recovery_waiters(rh
->context
);
632 EXPORT_SYMBOL_GPL(dm_rh_recovery_prepare
);
635 * Returns any quiesced regions.
637 struct dm_region
*dm_rh_recovery_start(struct dm_region_hash
*rh
)
639 struct dm_region
*reg
= NULL
;
641 spin_lock_irq(&rh
->region_lock
);
642 if (!list_empty(&rh
->quiesced_regions
)) {
643 reg
= list_entry(rh
->quiesced_regions
.next
,
644 struct dm_region
, list
);
645 list_del_init(®
->list
); /* remove from the quiesced list */
647 spin_unlock_irq(&rh
->region_lock
);
651 EXPORT_SYMBOL_GPL(dm_rh_recovery_start
);
653 void dm_rh_recovery_end(struct dm_region
*reg
, int success
)
655 struct dm_region_hash
*rh
= reg
->rh
;
657 spin_lock_irq(&rh
->region_lock
);
659 list_add(®
->list
, ®
->rh
->recovered_regions
);
661 list_add(®
->list
, ®
->rh
->failed_recovered_regions
);
663 spin_unlock_irq(&rh
->region_lock
);
665 rh
->wakeup_workers(rh
->context
);
667 EXPORT_SYMBOL_GPL(dm_rh_recovery_end
);
669 /* Return recovery in flight count. */
670 int dm_rh_recovery_in_flight(struct dm_region_hash
*rh
)
672 return atomic_read(&rh
->recovery_in_flight
);
674 EXPORT_SYMBOL_GPL(dm_rh_recovery_in_flight
);
676 int dm_rh_flush(struct dm_region_hash
*rh
)
678 return rh
->log
->type
->flush(rh
->log
);
680 EXPORT_SYMBOL_GPL(dm_rh_flush
);
682 void dm_rh_delay(struct dm_region_hash
*rh
, struct bio
*bio
)
684 struct dm_region
*reg
;
686 read_lock(&rh
->hash_lock
);
687 reg
= __rh_find(rh
, dm_rh_bio_to_region(rh
, bio
));
688 bio_list_add(®
->delayed_bios
, bio
);
689 read_unlock(&rh
->hash_lock
);
691 EXPORT_SYMBOL_GPL(dm_rh_delay
);
693 void dm_rh_stop_recovery(struct dm_region_hash
*rh
)
697 /* wait for any recovering regions */
698 for (i
= 0; i
< rh
->max_recovery
; i
++)
699 down(&rh
->recovery_count
);
701 EXPORT_SYMBOL_GPL(dm_rh_stop_recovery
);
703 void dm_rh_start_recovery(struct dm_region_hash
*rh
)
707 for (i
= 0; i
< rh
->max_recovery
; i
++)
708 up(&rh
->recovery_count
);
710 rh
->wakeup_workers(rh
->context
);
712 EXPORT_SYMBOL_GPL(dm_rh_start_recovery
);
714 MODULE_DESCRIPTION(DM_NAME
" region hash");
715 MODULE_AUTHOR("Joe Thornber/Heinz Mauelshagen <dm-devel@redhat.com>");
716 MODULE_LICENSE("GPL");