/*
 * raid5.c : Multiple Devices driver for Linux
 *	   Copyright (C) 1996, 1997 Ingo Molnar, Miguel de Icaza, Gadi Oxman
 *	   Copyright (C) 1999, 2000 Ingo Molnar
 *
 * RAID-5 management functions.
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2, or (at your option)
 * any later version.
 *
 * You should have received a copy of the GNU General Public License
 * (for example /usr/src/linux/COPYING); if not, write to the Free
 * Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 */


#include <linux/config.h>
#include <linux/module.h>
#include <linux/locks.h>
#include <linux/slab.h>
#include <linux/raid/raid5.h>
#include <asm/bitops.h>
#include <asm/atomic.h>

static mdk_personality_t raid5_personality;

/*
 * Stripe cache
 */

#define NR_STRIPES		256
#define	IO_THRESHOLD		1
#define HASH_PAGES		1
#define HASH_PAGES_ORDER	0
#define NR_HASH			(HASH_PAGES * PAGE_SIZE / sizeof(struct stripe_head *))
#define HASH_MASK		(NR_HASH - 1)
#define stripe_hash(conf, sect)	((conf)->stripe_hashtbl[((sect) / ((conf)->buffer_size >> 9)) & HASH_MASK])

/*
 * The following can be used to debug the driver
 */
#define RAID5_DEBUG	0
#define RAID5_PARANOIA	1
#if RAID5_PARANOIA && CONFIG_SMP
# define CHECK_DEVLOCK() if (!spin_is_locked(&conf->device_lock)) BUG()
#else
# define CHECK_DEVLOCK()
#endif

#if RAID5_DEBUG
#define PRINTK(x...) printk(x)
#define inline
#define __inline__
#else
#define PRINTK(x...) do { } while (0)
#endif

static void print_raid5_conf (raid5_conf_t *conf);

static inline void __release_stripe(raid5_conf_t *conf, struct stripe_head *sh)
{
	if (atomic_dec_and_test(&sh->count)) {
		if (!list_empty(&sh->lru))
			BUG();
		if (atomic_read(&conf->active_stripes)==0)
			BUG();
		if (test_bit(STRIPE_HANDLE, &sh->state)) {
			if (test_bit(STRIPE_DELAYED, &sh->state))
				list_add_tail(&sh->lru, &conf->delayed_list);
			else
				list_add_tail(&sh->lru, &conf->handle_list);
			md_wakeup_thread(conf->thread);
		} else {
			if (test_and_clear_bit(STRIPE_PREREAD_ACTIVE, &sh->state)) {
				atomic_dec(&conf->preread_active_stripes);
				if (atomic_read(&conf->preread_active_stripes) < IO_THRESHOLD)
					md_wakeup_thread(conf->thread);
			}
			list_add_tail(&sh->lru, &conf->inactive_list);
			atomic_dec(&conf->active_stripes);
			if (!conf->inactive_blocked ||
			    atomic_read(&conf->active_stripes) < (NR_STRIPES*3/4))
				wake_up(&conf->wait_for_stripe);
		}
	}
}
static void release_stripe(struct stripe_head *sh)
{
	raid5_conf_t *conf = sh->raid_conf;
	unsigned long flags;
	
	spin_lock_irqsave(&conf->device_lock, flags);
	__release_stripe(conf, sh);
	spin_unlock_irqrestore(&conf->device_lock, flags);
}

static void remove_hash(struct stripe_head *sh)
{
	PRINTK("remove_hash(), stripe %lu\n", sh->sector);

	if (sh->hash_pprev) {
		if (sh->hash_next)
			sh->hash_next->hash_pprev = sh->hash_pprev;
		*sh->hash_pprev = sh->hash_next;
		sh->hash_pprev = NULL;
	}
}

static __inline__ void insert_hash(raid5_conf_t *conf, struct stripe_head *sh)
{
	struct stripe_head **shp = &stripe_hash(conf, sh->sector);

	PRINTK("insert_hash(), stripe %lu\n",sh->sector);

	CHECK_DEVLOCK();
	if ((sh->hash_next = *shp) != NULL)
		(*shp)->hash_pprev = &sh->hash_next;
	*shp = sh;
	sh->hash_pprev = shp;
}


/* find an idle stripe, make sure it is unhashed, and return it. */
static struct stripe_head *get_free_stripe(raid5_conf_t *conf)
{
	struct stripe_head *sh = NULL;
	struct list_head *first;

	CHECK_DEVLOCK();
	if (list_empty(&conf->inactive_list))
		goto out;
	first = conf->inactive_list.next;
	sh = list_entry(first, struct stripe_head, lru);
	list_del_init(first);
	remove_hash(sh);
	atomic_inc(&conf->active_stripes);
out:
	return sh;
}

static void shrink_buffers(struct stripe_head *sh, int num)
{
	struct buffer_head *bh;
	int i;

	for (i=0; i<num ; i++) {
		bh = sh->bh_cache[i];
		if (!bh)
			return;
		sh->bh_cache[i] = NULL;
		free_page((unsigned long) bh->b_data);
		kfree(bh);
	}
}

static int grow_buffers(struct stripe_head *sh, int num, int b_size, int priority)
{
	struct buffer_head *bh;
	int i;

	for (i=0; i<num; i++) {
		struct page *page;
		bh = kmalloc(sizeof(struct buffer_head), priority);
		if (!bh)
			return 1;
		memset(bh, 0, sizeof (struct buffer_head));
		init_waitqueue_head(&bh->b_wait);
		if ((page = alloc_page(priority)))
			bh->b_data = page_address(page);
		else {
			kfree(bh);
			return 1;
		}
		atomic_set(&bh->b_count, 0);
		bh->b_page = page;
		sh->bh_cache[i] = bh;

	}
	return 0;
}

static struct buffer_head *raid5_build_block (struct stripe_head *sh, int i);

static inline void init_stripe(struct stripe_head *sh, unsigned long sector)
{
	raid5_conf_t *conf = sh->raid_conf;
	int disks = conf->raid_disks, i;

	if (atomic_read(&sh->count) != 0)
		BUG();
	if (test_bit(STRIPE_HANDLE, &sh->state))
		BUG();
	
	CHECK_DEVLOCK();
	PRINTK("init_stripe called, stripe %lu\n", sh->sector);

	remove_hash(sh);
	
	sh->sector = sector;
	sh->size = conf->buffer_size;
	sh->state = 0;

	for (i=disks; i--; ) {
		if (sh->bh_read[i] || sh->bh_write[i] || sh->bh_written[i] ||
		    buffer_locked(sh->bh_cache[i])) {
			printk("sector=%lx i=%d %p %p %p %d\n",
			       sh->sector, i, sh->bh_read[i],
			       sh->bh_write[i], sh->bh_written[i],
			       buffer_locked(sh->bh_cache[i]));
			BUG();
		}
		clear_bit(BH_Uptodate, &sh->bh_cache[i]->b_state);
		raid5_build_block(sh, i);
	}
	insert_hash(conf, sh);
}

/* the buffer size has changed, so unhash all stripes
 * as active stripes complete, they will go onto inactive list
 */
static void shrink_stripe_cache(raid5_conf_t *conf)
{
	int i;
	CHECK_DEVLOCK();
	if (atomic_read(&conf->active_stripes))
		BUG();
	for (i=0; i < NR_HASH; i++) {
		struct stripe_head *sh;
		while ((sh = conf->stripe_hashtbl[i])) 
			remove_hash(sh);
	}
}

static struct stripe_head *__find_stripe(raid5_conf_t *conf, unsigned long sector)
{
	struct stripe_head *sh;

	CHECK_DEVLOCK();
	PRINTK("__find_stripe, sector %lu\n", sector);
	for (sh = stripe_hash(conf, sector); sh; sh = sh->hash_next)
		if (sh->sector == sector)
			return sh;
	PRINTK("__stripe %lu not in cache\n", sector);
	return NULL;
}

static struct stripe_head *get_active_stripe(raid5_conf_t *conf, unsigned long sector, int size, int noblock) 
{
	struct stripe_head *sh;

	PRINTK("get_stripe, sector %lu\n", sector);

	md_spin_lock_irq(&conf->device_lock);

	do {
		if (conf->buffer_size == 0 ||
		    (size && size != conf->buffer_size)) {
			/* either the size is being changed (buffer_size==0) or
			 * we need to change it.
			 * If size==0, we can proceed as soon as buffer_size gets set.
			 * If size>0, we can proceed when active_stripes reaches 0, or
			 * when someone else sets the buffer_size to size.
			 * If someone sets the buffer size to something else, we will need to
			 * assert that we want to change it again
			 */
			int oldsize = conf->buffer_size;
			PRINTK("get_stripe %ld/%d buffer_size is %d, %d active\n", sector, size, conf->buffer_size, atomic_read(&conf->active_stripes));
			if (size==0)
				wait_event_lock_irq(conf->wait_for_stripe,
						    conf->buffer_size,
						    conf->device_lock);
			else {
				while (conf->buffer_size != size && atomic_read(&conf->active_stripes)) {
					conf->buffer_size = 0;
					wait_event_lock_irq(conf->wait_for_stripe,
							    atomic_read(&conf->active_stripes)==0 || conf->buffer_size,
							    conf->device_lock);
					PRINTK("waited and now  %ld/%d buffer_size is %d - %d active\n", sector, size,
					       conf->buffer_size, atomic_read(&conf->active_stripes));
				}

				if (conf->buffer_size != size) {
					PRINTK("raid5: switching cache buffer size, %d --> %d\n", oldsize, size);
					shrink_stripe_cache(conf);
					if (size==0) BUG();
					conf->buffer_size = size;
					PRINTK("size now %d\n", conf->buffer_size);
				}
			}
		}
		if (size == 0)
			sector -= sector & ((conf->buffer_size>>9)-1);

		sh = __find_stripe(conf, sector);
		if (!sh) {
			if (!conf->inactive_blocked)
				sh = get_free_stripe(conf);
			if (noblock && sh == NULL)
				break;
			if (!sh) {
				conf->inactive_blocked = 1;
				wait_event_lock_irq(conf->wait_for_stripe,
						    !list_empty(&conf->inactive_list) &&
						    (atomic_read(&conf->active_stripes) < (NR_STRIPES *3/4)
						     || !conf->inactive_blocked),
						    conf->device_lock);
				conf->inactive_blocked = 0;
			} else
				init_stripe(sh, sector);
		} else {
			if (atomic_read(&sh->count)) {
				if (!list_empty(&sh->lru))
					BUG();
			} else {
				if (!test_bit(STRIPE_HANDLE, &sh->state))
					atomic_inc(&conf->active_stripes);
				if (list_empty(&sh->lru))
					BUG();
				list_del_init(&sh->lru);
			}
		}
	} while (sh == NULL);

	if (sh)
		atomic_inc(&sh->count);

	md_spin_unlock_irq(&conf->device_lock);
	return sh;
}

static int grow_stripes(raid5_conf_t *conf, int num, int priority)
{
	struct stripe_head *sh;

	while (num--) {
		sh = kmalloc(sizeof(struct stripe_head), priority);
		if (!sh)
			return 1;
		memset(sh, 0, sizeof(*sh));
		sh->raid_conf = conf;
		sh->lock = SPIN_LOCK_UNLOCKED;

		if (grow_buffers(sh, conf->raid_disks, PAGE_SIZE, priority)) {
			shrink_buffers(sh, conf->raid_disks);
			kfree(sh);
			return 1;
		}
		/* we just created an active stripe so... */
		atomic_set(&sh->count, 1);
		atomic_inc(&conf->active_stripes);
		INIT_LIST_HEAD(&sh->lru);
		release_stripe(sh);
	}
	return 0;
}

static void shrink_stripes(raid5_conf_t *conf, int num)
{
	struct stripe_head *sh;

	while (num--) {
		spin_lock_irq(&conf->device_lock);
		sh = get_free_stripe(conf);
		spin_unlock_irq(&conf->device_lock);
		if (!sh)
			break;
		if (atomic_read(&sh->count))
			BUG();
		shrink_buffers(sh, conf->raid_disks);
		kfree(sh);
		atomic_dec(&conf->active_stripes);
	}
}


static void raid5_end_read_request (struct buffer_head * bh, int uptodate)
{
 	struct stripe_head *sh = bh->b_private;
	raid5_conf_t *conf = sh->raid_conf;
	int disks = conf->raid_disks, i;
	unsigned long flags;

	for (i=0 ; i<disks; i++)
		if (bh == sh->bh_cache[i])
			break;

	PRINTK("end_read_request %lu/%d, count: %d, uptodate %d.\n", sh->sector, i, atomic_read(&sh->count), uptodate);
	if (i == disks) {
		BUG();
		return;
	}

	if (uptodate) {
		struct buffer_head *buffer;
		spin_lock_irqsave(&conf->device_lock, flags);
		/* we can return a buffer if we bypassed the cache or
		 * if the top buffer is not in highmem.  If there are
		 * multiple buffers, leave the extra work to
		 * handle_stripe
		 */
		buffer = sh->bh_read[i];
		if (buffer &&
		    (!PageHighMem(buffer->b_page)
		     || buffer->b_page == bh->b_page )
			) {
			sh->bh_read[i] = buffer->b_reqnext;
			buffer->b_reqnext = NULL;
		} else
			buffer = NULL;
		spin_unlock_irqrestore(&conf->device_lock, flags);
		if (sh->bh_page[i]==NULL)
			set_bit(BH_Uptodate, &bh->b_state);
		if (buffer) {
			if (buffer->b_page != bh->b_page)
				memcpy(buffer->b_data, bh->b_data, bh->b_size);
			buffer->b_end_io(buffer, 1);
		}
	} else {
		md_error(conf->mddev, bh->b_dev);
		clear_bit(BH_Uptodate, &bh->b_state);
	}
	/* must restore b_page before unlocking buffer... */
	if (sh->bh_page[i]) {
		bh->b_page = sh->bh_page[i];
		bh->b_data = page_address(bh->b_page);
		sh->bh_page[i] = NULL;
		clear_bit(BH_Uptodate, &bh->b_state);
	}
	clear_bit(BH_Lock, &bh->b_state);
	set_bit(STRIPE_HANDLE, &sh->state);
	release_stripe(sh);
}

static void raid5_end_write_request (struct buffer_head *bh, int uptodate)
{
 	struct stripe_head *sh = bh->b_private;
	raid5_conf_t *conf = sh->raid_conf;
	int disks = conf->raid_disks, i;
	unsigned long flags;

	for (i=0 ; i<disks; i++)
		if (bh == sh->bh_cache[i])
			break;

	PRINTK("end_write_request %lu/%d, count %d, uptodate: %d.\n", sh->sector, i, atomic_read(&sh->count), uptodate);
	if (i == disks) {
		BUG();
		return;
	}

	md_spin_lock_irqsave(&conf->device_lock, flags);
	if (!uptodate)
		md_error(conf->mddev, bh->b_dev);
	clear_bit(BH_Lock, &bh->b_state);
	set_bit(STRIPE_HANDLE, &sh->state);
	__release_stripe(conf, sh);
	md_spin_unlock_irqrestore(&conf->device_lock, flags);
}
	


static struct buffer_head *raid5_build_block (struct stripe_head *sh, int i)
{
	raid5_conf_t *conf = sh->raid_conf;
	struct buffer_head *bh = sh->bh_cache[i];
	unsigned long block = sh->sector / (sh->size >> 9);

	init_buffer(bh, raid5_end_read_request, sh);
	bh->b_dev       = conf->disks[i].dev;
	bh->b_blocknr   = block;

	bh->b_state	= (1 << BH_Req) | (1 << BH_Mapped);
	bh->b_size	= sh->size;
	bh->b_list	= BUF_LOCKED;
	return bh;
}

static int raid5_error (mddev_t *mddev, kdev_t dev)
{
	raid5_conf_t *conf = (raid5_conf_t *) mddev->private;
	mdp_super_t *sb = mddev->sb;
	struct disk_info *disk;
	int i;

	PRINTK("raid5_error called\n");

	for (i = 0, disk = conf->disks; i < conf->raid_disks; i++, disk++) {
		if (disk->dev == dev) {
			if (disk->operational) {
				disk->operational = 0;
				mark_disk_faulty(sb->disks+disk->number);
				mark_disk_nonsync(sb->disks+disk->number);
				mark_disk_inactive(sb->disks+disk->number);
				sb->active_disks--;
				sb->working_disks--;
				sb->failed_disks++;
				mddev->sb_dirty = 1;
				conf->working_disks--;
				conf->failed_disks++;
				md_wakeup_thread(conf->thread);
				printk (KERN_ALERT
					"raid5: Disk failure on %s, disabling device."
					" Operation continuing on %d devices\n",
					partition_name (dev), conf->working_disks);
			}
			return 0;
		}
	}
	/*
	 * handle errors in spares (during reconstruction)
	 */
	if (conf->spare) {
		disk = conf->spare;
		if (disk->dev == dev) {
			printk (KERN_ALERT
				"raid5: Disk failure on spare %s\n",
				partition_name (dev));
			if (!conf->spare->operational) {
				/* probably a SET_DISK_FAULTY ioctl */
				return -EIO;
			}
			disk->operational = 0;
			disk->write_only = 0;
			conf->spare = NULL;
			mark_disk_faulty(sb->disks+disk->number);
			mark_disk_nonsync(sb->disks+disk->number);
			mark_disk_inactive(sb->disks+disk->number);
			sb->spare_disks--;
			sb->working_disks--;
			sb->failed_disks++;

			mddev->sb_dirty = 1;
			md_wakeup_thread(conf->thread);

			return 0;
		}
	}
	MD_BUG();
	return -EIO;
}	

/*
 * Input: a 'big' sector number,
 * Output: index of the data and parity disk, and the sector # in them.
 */
static unsigned long raid5_compute_sector(unsigned long r_sector, unsigned int raid_disks,
			unsigned int data_disks, unsigned int * dd_idx,
			unsigned int * pd_idx, raid5_conf_t *conf)
{
	unsigned long stripe;
	unsigned long chunk_number;
	unsigned int chunk_offset;
	unsigned long new_sector;
	int sectors_per_chunk = conf->chunk_size >> 9;

	/* First compute the information on this sector */

	/*
	 * Compute the chunk number and the sector offset inside the chunk
	 */
	chunk_number = r_sector / sectors_per_chunk;
	chunk_offset = r_sector % sectors_per_chunk;

	/*
	 * Compute the stripe number
	 */
	stripe = chunk_number / data_disks;

	/*
	 * Compute the data disk and parity disk indexes inside the stripe
	 */
	*dd_idx = chunk_number % data_disks;

	/*
	 * Select the parity disk based on the user selected algorithm.
	 */
	if (conf->level == 4)
		*pd_idx = data_disks;
	else switch (conf->algorithm) {
		case ALGORITHM_LEFT_ASYMMETRIC:
			*pd_idx = data_disks - stripe % raid_disks;
			if (*dd_idx >= *pd_idx)
				(*dd_idx)++;
			break;
		case ALGORITHM_RIGHT_ASYMMETRIC:
			*pd_idx = stripe % raid_disks;
			if (*dd_idx >= *pd_idx)
				(*dd_idx)++;
			break;
		case ALGORITHM_LEFT_SYMMETRIC:
			*pd_idx = data_disks - stripe % raid_disks;
			*dd_idx = (*pd_idx + 1 + *dd_idx) % raid_disks;
			break;
		case ALGORITHM_RIGHT_SYMMETRIC:
			*pd_idx = stripe % raid_disks;
			*dd_idx = (*pd_idx + 1 + *dd_idx) % raid_disks;
			break;
		default:
			printk ("raid5: unsupported algorithm %d\n", conf->algorithm);
	}

	/*
	 * Finally, compute the new sector number
	 */
	new_sector = stripe * sectors_per_chunk + chunk_offset;
	return new_sector;
}

#if 0
static unsigned long compute_blocknr(struct stripe_head *sh, int i)
{
	raid5_conf_t *conf = sh->raid_conf;
	int raid_disks = conf->raid_disks, data_disks = raid_disks - 1;
	unsigned long new_sector = sh->sector, check;
	int sectors_per_chunk = conf->chunk_size >> 9;
	unsigned long stripe = new_sector / sectors_per_chunk;
	int chunk_offset = new_sector % sectors_per_chunk;
	int chunk_number, dummy1, dummy2, dd_idx = i;
	unsigned long r_sector, blocknr;

	switch (conf->algorithm) {
		case ALGORITHM_LEFT_ASYMMETRIC:
		case ALGORITHM_RIGHT_ASYMMETRIC:
			if (i > sh->pd_idx)
				i--;
			break;
		case ALGORITHM_LEFT_SYMMETRIC:
		case ALGORITHM_RIGHT_SYMMETRIC:
			if (i < sh->pd_idx)
				i += raid_disks;
			i -= (sh->pd_idx + 1);
			break;
		default:
			printk ("raid5: unsupported algorithm %d\n", conf->algorithm);
	}

	chunk_number = stripe * data_disks + i;
	r_sector = chunk_number * sectors_per_chunk + chunk_offset;
	blocknr = r_sector / (sh->size >> 9);

	check = raid5_compute_sector (r_sector, raid_disks, data_disks, &dummy1, &dummy2, conf);
	if (check != sh->sector || dummy1 != dd_idx || dummy2 != sh->pd_idx) {
		printk("compute_blocknr: map not correct\n");
		return 0;
	}
	return blocknr;
}
#endif

#define check_xor() 	do { 					\
			   if (count == MAX_XOR_BLOCKS) {	\
				xor_block(count, bh_ptr);	\
				count = 1;			\
			   }					\
			} while(0)


static void compute_block(struct stripe_head *sh, int dd_idx)
{
	raid5_conf_t *conf = sh->raid_conf;
	int i, count, disks = conf->raid_disks;
	struct buffer_head *bh_ptr[MAX_XOR_BLOCKS], *bh;

	PRINTK("compute_block, stripe %lu, idx %d\n", sh->sector, dd_idx);


	memset(sh->bh_cache[dd_idx]->b_data, 0, sh->size);
	bh_ptr[0] = sh->bh_cache[dd_idx];
	count = 1;
	for (i = disks ; i--; ) {
		if (i == dd_idx)
			continue;
		bh = sh->bh_cache[i];
		if (buffer_uptodate(bh))
			bh_ptr[count++] = bh;
		else
			printk("compute_block() %d, stripe %lu, %d not present\n", dd_idx, sh->sector, i);

		check_xor();
	}
	if (count != 1)
		xor_block(count, bh_ptr);
	set_bit(BH_Uptodate, &sh->bh_cache[dd_idx]->b_state);
}

static void compute_parity(struct stripe_head *sh, int method)
{
	raid5_conf_t *conf = sh->raid_conf;
	int i, pd_idx = sh->pd_idx, disks = conf->raid_disks, count;
	struct buffer_head *bh_ptr[MAX_XOR_BLOCKS];
	struct buffer_head *chosen[MD_SB_DISKS];

	PRINTK("compute_parity, stripe %lu, method %d\n", sh->sector, method);
	memset(chosen, 0, sizeof(chosen));

	count = 1;
	bh_ptr[0] = sh->bh_cache[pd_idx];
	switch(method) {
	case READ_MODIFY_WRITE:
		if (!buffer_uptodate(sh->bh_cache[pd_idx]))
			BUG();
		for (i=disks ; i-- ;) {
			if (i==pd_idx)
				continue;
			if (sh->bh_write[i] &&
			    buffer_uptodate(sh->bh_cache[i])) {
				bh_ptr[count++] = sh->bh_cache[i];
				chosen[i] = sh->bh_write[i];
				sh->bh_write[i] = sh->bh_write[i]->b_reqnext;
				chosen[i]->b_reqnext = sh->bh_written[i];
				sh->bh_written[i] = chosen[i];
				check_xor();
			}
		}
		break;
	case RECONSTRUCT_WRITE:
		memset(sh->bh_cache[pd_idx]->b_data, 0, sh->size);
		for (i= disks; i-- ;)
			if (i!=pd_idx && sh->bh_write[i]) {
				chosen[i] = sh->bh_write[i];
				sh->bh_write[i] = sh->bh_write[i]->b_reqnext;
				chosen[i]->b_reqnext = sh->bh_written[i];
				sh->bh_written[i] = chosen[i];
			}
		break;
	case CHECK_PARITY:
		break;
	}
	if (count>1) {
		xor_block(count, bh_ptr);
		count = 1;
	}
	
	for (i = disks; i--;)
		if (chosen[i]) {
			struct buffer_head *bh = sh->bh_cache[i];
			char *bdata;
			bdata = bh_kmap(chosen[i]);
			memcpy(bh->b_data,
			       bdata,sh->size);
			bh_kunmap(chosen[i]);
			set_bit(BH_Lock, &bh->b_state);
			mark_buffer_uptodate(bh, 1);
		}

	switch(method) {
	case RECONSTRUCT_WRITE:
	case CHECK_PARITY:
		for (i=disks; i--;)
			if (i != pd_idx) {
				bh_ptr[count++] = sh->bh_cache[i];
				check_xor();
			}
		break;
	case READ_MODIFY_WRITE:
		for (i = disks; i--;)
			if (chosen[i]) {
				bh_ptr[count++] = sh->bh_cache[i];
				check_xor();
			}
	}
	if (count != 1)
		xor_block(count, bh_ptr);
	
	if (method != CHECK_PARITY) {
		mark_buffer_uptodate(sh->bh_cache[pd_idx], 1);
		set_bit(BH_Lock, &sh->bh_cache[pd_idx]->b_state);
	} else
		mark_buffer_uptodate(sh->bh_cache[pd_idx], 0);
}

static void add_stripe_bh (struct stripe_head *sh, struct buffer_head *bh, int dd_idx, int rw)
{
	struct buffer_head **bhp;
	raid5_conf_t *conf = sh->raid_conf;

	PRINTK("adding bh b#%lu to stripe s#%lu\n", bh->b_blocknr, sh->sector);


	spin_lock(&sh->lock);
	spin_lock_irq(&conf->device_lock);
	bh->b_reqnext = NULL;
	if (rw == READ)
		bhp = &sh->bh_read[dd_idx];
	else
		bhp = &sh->bh_write[dd_idx];
	while (*bhp) {
		printk(KERN_NOTICE "raid5: multiple %d requests for sector %ld\n", rw, sh->sector);
		bhp = & (*bhp)->b_reqnext;
	}
	*bhp = bh;
	spin_unlock_irq(&conf->device_lock);
	spin_unlock(&sh->lock);

	PRINTK("added bh b#%lu to stripe s#%lu, disk %d.\n", bh->b_blocknr, sh->sector, dd_idx);
}





/*
 * handle_stripe - do things to a stripe.
 *
 * We lock the stripe and then examine the state of various bits
 * to see what needs to be done.
 * Possible results:
 *    return some read request which now have data
 *    return some write requests which are safely on disc
 *    schedule a read on some buffers
 *    schedule a write of some buffers
 *    return confirmation of parity correctness
 *
 * Parity calculations are done inside the stripe lock
 * buffers are taken off read_list or write_list, and bh_cache buffers
 * get BH_Lock set before the stripe lock is released.
 *
 */
 
static void handle_stripe(struct stripe_head *sh)
{
	raid5_conf_t *conf = sh->raid_conf;
	int disks = conf->raid_disks;
	struct buffer_head *return_ok= NULL, *return_fail = NULL;
	int action[MD_SB_DISKS];
	int i;
	int syncing;
	int locked=0, uptodate=0, to_read=0, to_write=0, failed=0, written=0;
	int failed_num=0;
	struct buffer_head *bh;

	PRINTK("handling stripe %ld, cnt=%d, pd_idx=%d\n", sh->sector, atomic_read(&sh->count), sh->pd_idx);
	memset(action, 0, sizeof(action));

	spin_lock(&sh->lock);
	clear_bit(STRIPE_HANDLE, &sh->state);
	clear_bit(STRIPE_DELAYED, &sh->state);

	syncing = test_bit(STRIPE_SYNCING, &sh->state);
	/* Now to look around and see what can be done */

	for (i=disks; i--; ) {
		bh = sh->bh_cache[i];
		PRINTK("check %d: state 0x%lx read %p write %p written %p\n", i, bh->b_state, sh->bh_read[i], sh->bh_write[i], sh->bh_written[i]);
		/* maybe we can reply to a read */
		if (buffer_uptodate(bh) && sh->bh_read[i]) {
			struct buffer_head *rbh, *rbh2;
			PRINTK("Return read for disc %d\n", i);
			spin_lock_irq(&conf->device_lock);
			rbh = sh->bh_read[i];
			sh->bh_read[i] = NULL;
			spin_unlock_irq(&conf->device_lock);
			while (rbh) {
				char *bdata;
				bdata = bh_kmap(rbh);
				memcpy(bdata, bh->b_data, bh->b_size);
				bh_kunmap(rbh);
				rbh2 = rbh->b_reqnext;
				rbh->b_reqnext = return_ok;
				return_ok = rbh;
				rbh = rbh2;
			}
		}

		/* now count some things */
		if (buffer_locked(bh)) locked++;
		if (buffer_uptodate(bh)) uptodate++;

		
		if (sh->bh_read[i]) to_read++;
		if (sh->bh_write[i]) to_write++;
		if (sh->bh_written[i]) written++;
		if (!conf->disks[i].operational) {
			failed++;
			failed_num = i;
		}
	}
	PRINTK("locked=%d uptodate=%d to_read=%d to_write=%d failed=%d failed_num=%d\n",
	       locked, uptodate, to_read, to_write, failed, failed_num);
	/* check if the array has lost two devices and, if so, some requests might
	 * need to be failed
	 */
	if (failed > 1 && to_read+to_write+written) {
		for (i=disks; i--; ) {
			/* fail all writes first */
			if (sh->bh_write[i]) to_write--;
			while ((bh = sh->bh_write[i])) {
				sh->bh_write[i] = bh->b_reqnext;
				bh->b_reqnext = return_fail;
				return_fail = bh;
			}
			/* and fail all 'written' */
			if (sh->bh_written[i]) written--;
			while ((bh = sh->bh_written[i])) {
				sh->bh_written[i] = bh->b_reqnext;
				bh->b_reqnext = return_fail;
				return_fail = bh;
			}

			/* fail any reads if this device is non-operational */
			if (!conf->disks[i].operational) {
				spin_lock_irq(&conf->device_lock);
				if (sh->bh_read[i]) to_read--;
				while ((bh = sh->bh_read[i])) {
					sh->bh_read[i] = bh->b_reqnext;
					bh->b_reqnext = return_fail;
					return_fail = bh;
				}
				spin_unlock_irq(&conf->device_lock);
			}
		}
	}
	if (failed > 1 && syncing) {
		md_done_sync(conf->mddev, (sh->size>>9) - sh->sync_redone,0);
		clear_bit(STRIPE_SYNCING, &sh->state);
		syncing = 0;
	}

	/* might be able to return some write requests if the parity block
	 * is safe, or on a failed drive
	 */
	bh = sh->bh_cache[sh->pd_idx];
	if ( written &&
	     ( (conf->disks[sh->pd_idx].operational && !buffer_locked(bh) && buffer_uptodate(bh))
	       || (failed == 1 && failed_num == sh->pd_idx))
	    ) {
	    /* any written block on a uptodate or failed drive can be returned */
	    for (i=disks; i--; )
		if (sh->bh_written[i]) {
		    bh = sh->bh_cache[i];
		    if (!conf->disks[sh->pd_idx].operational ||
			(!buffer_locked(bh) && buffer_uptodate(bh)) ) {
			/* maybe we can return some write requests */
			struct buffer_head *wbh, *wbh2;
			PRINTK("Return write for disc %d\n", i);
			wbh = sh->bh_written[i];
			sh->bh_written[i] = NULL;
			while (wbh) {
			    wbh2 = wbh->b_reqnext;
			    wbh->b_reqnext = return_ok;
			    return_ok = wbh;
			    wbh = wbh2;
			}
		    }
		}
	}
		
	/* Now we might consider reading some blocks, either to check/generate
	 * parity, or to satisfy requests
	 */
	if (to_read || (syncing && (uptodate < disks))) {
		for (i=disks; i--;) {
			bh = sh->bh_cache[i];
			if (!buffer_locked(bh) && !buffer_uptodate(bh) &&
			    (sh->bh_read[i] || syncing || (failed && sh->bh_read[failed_num]))) {
				/* we would like to get this block, possibly
				 * by computing it, but we might not be able to
				 */
				if (uptodate == disks-1) {
					PRINTK("Computing block %d\n", i);
					compute_block(sh, i);
					uptodate++;
				} else if (conf->disks[i].operational) {
					set_bit(BH_Lock, &bh->b_state);
					action[i] = READ+1;
					/* if I am just reading this block and we don't have
					   a failed drive, or any pending writes then sidestep the cache */
					if (sh->bh_page[i]) BUG();
					if (sh->bh_read[i] && !sh->bh_read[i]->b_reqnext &&
					    ! syncing && !failed && !to_write) {
						sh->bh_page[i] = sh->bh_cache[i]->b_page;
						sh->bh_cache[i]->b_page =  sh->bh_read[i]->b_page;
						sh->bh_cache[i]->b_data =  sh->bh_read[i]->b_data;
					}
					locked++;
					PRINTK("Reading block %d (sync=%d)\n", i, syncing);
					if (syncing)
						md_sync_acct(conf->disks[i].dev, bh->b_size>>9);
				}
			}
		}
		set_bit(STRIPE_HANDLE, &sh->state);
	}

	/* now to consider writing and what else, if anything should be read */
	if (to_write) {
		int rmw=0, rcw=0;
		for (i=disks ; i--;) {
			/* would I have to read this buffer for read_modify_write */
			bh = sh->bh_cache[i];
			if ((sh->bh_write[i] || i == sh->pd_idx) &&
			    (!buffer_locked(bh) || sh->bh_page[i]) &&
			    !buffer_uptodate(bh)) {
				if (conf->disks[i].operational 
/*				    && !(conf->resync_parity && i == sh->pd_idx) */
					)
					rmw++;
				else rmw += 2*disks;  /* cannot read it */
			}
			/* Would I have to read this buffer for reconstruct_write */
			if (!sh->bh_write[i] && i != sh->pd_idx &&
			    (!buffer_locked(bh) || sh->bh_page[i]) &&
			    !buffer_uptodate(bh)) {
				if (conf->disks[i].operational) rcw++;
				else rcw += 2*disks;
			}
		}
		PRINTK("for sector %ld, rmw=%d rcw=%d\n", sh->sector, rmw, rcw);
		set_bit(STRIPE_HANDLE, &sh->state);
		if (rmw < rcw && rmw > 0)
			/* prefer read-modify-write, but need to get some data */
			for (i=disks; i--;) {
				bh = sh->bh_cache[i];
				if ((sh->bh_write[i] || i == sh->pd_idx) &&
				    !buffer_locked(bh) && !buffer_uptodate(bh) &&
				    conf->disks[i].operational) {
					if (test_bit(STRIPE_PREREAD_ACTIVE, &sh->state))
					{
						PRINTK("Read_old block %d for r-m-w\n", i);
						set_bit(BH_Lock, &bh->b_state);
						action[i] = READ+1;
						locked++;
					} else {
						set_bit(STRIPE_DELAYED, &sh->state);
						set_bit(STRIPE_HANDLE, &sh->state);
					}
				}
			}
		if (rcw <= rmw && rcw > 0)
			/* want reconstruct write, but need to get some data */
			for (i=disks; i--;) {
				bh = sh->bh_cache[i];
				if (!sh->bh_write[i]  && i != sh->pd_idx &&
				    !buffer_locked(bh) && !buffer_uptodate(bh) &&
				    conf->disks[i].operational) {
					if (test_bit(STRIPE_PREREAD_ACTIVE, &sh->state))
					{
						PRINTK("Read_old block %d for Reconstruct\n", i);
						set_bit(BH_Lock, &bh->b_state);
						action[i] = READ+1;
						locked++;
					} else {
						set_bit(STRIPE_DELAYED, &sh->state);
						set_bit(STRIPE_HANDLE, &sh->state);
					}
				}
			}
		/* now if nothing is locked, and if we have enough data, we can start a write request */
		if (locked == 0 && (rcw == 0 ||rmw == 0)) {
			PRINTK("Computing parity...\n");
			compute_parity(sh, rcw==0 ? RECONSTRUCT_WRITE : READ_MODIFY_WRITE);
			/* now every locked buffer is ready to be written */
			for (i=disks; i--;)
				if (buffer_locked(sh->bh_cache[i])) {
					PRINTK("Writing block %d\n", i);
					locked++;
					action[i] = WRITE+1;
					if (!conf->disks[i].operational
					    || (i==sh->pd_idx && failed == 0))
						set_bit(STRIPE_INSYNC, &sh->state);
				}
			if (test_and_clear_bit(STRIPE_PREREAD_ACTIVE, &sh->state)) {
				atomic_dec(&conf->preread_active_stripes);
				if (atomic_read(&conf->preread_active_stripes) < IO_THRESHOLD)
					md_wakeup_thread(conf->thread);
			}
		}
	}

	/* maybe we need to check and possibly fix the parity for this stripe
	 * Any reads will already have been scheduled, so we just see if enough data
	 * is available
	 */
	if (syncing && locked == 0 &&
	    !test_bit(STRIPE_INSYNC, &sh->state) && failed <= 1) {
		set_bit(STRIPE_HANDLE, &sh->state);
		if (failed == 0) {
			if (uptodate != disks)
				BUG();
			compute_parity(sh, CHECK_PARITY);
			uptodate--;
			bh = sh->bh_cache[sh->pd_idx];
			if ((*(u32*)bh->b_data) == 0 &&
			    !memcmp(bh->b_data, bh->b_data+4, bh->b_size-4)) {
				/* parity is correct (on disc, not in buffer any more) */
				set_bit(STRIPE_INSYNC, &sh->state);
			}
		}
		if (!test_bit(STRIPE_INSYNC, &sh->state)) {
			struct disk_info *spare;
			if (failed==0)
				failed_num = sh->pd_idx;
			/* should be able to compute the missing block and write it to spare */
			if (!buffer_uptodate(sh->bh_cache[failed_num])) {
				if (uptodate+1 != disks)
					BUG();
				compute_block(sh, failed_num);
				uptodate++;
			}
			if (uptodate != disks)
				BUG();
			bh = sh->bh_cache[failed_num];
			set_bit(BH_Lock, &bh->b_state);
			action[failed_num] = WRITE+1;
			locked++;
			set_bit(STRIPE_INSYNC, &sh->state);
			if (conf->disks[failed_num].operational)
				md_sync_acct(conf->disks[failed_num].dev, bh->b_size>>9);
			else if ((spare=conf->spare))
				md_sync_acct(spare->dev, bh->b_size>>9);

		}
	}
	if (syncing && locked == 0 && test_bit(STRIPE_INSYNC, &sh->state)) {
		md_done_sync(conf->mddev, (sh->size>>9) - sh->sync_redone,1);
		clear_bit(STRIPE_SYNCING, &sh->state);
	}
	
	
	spin_unlock(&sh->lock);

	while ((bh=return_ok)) {
		return_ok = bh->b_reqnext;
		bh->b_reqnext = NULL;
		bh->b_end_io(bh, 1);
	}
	while ((bh=return_fail)) {
		return_fail = bh->b_reqnext;
		bh->b_reqnext = NULL;
		bh->b_end_io(bh, 0);
	}
	for (i=disks; i-- ;) 
		if (action[i]) {
			struct buffer_head *bh = sh->bh_cache[i];
			struct disk_info *spare = conf->spare;
			int skip = 0;
			if (action[i] == READ+1)
				bh->b_end_io = raid5_end_read_request;
			else
				bh->b_end_io = raid5_end_write_request;
			if (conf->disks[i].operational)
				bh->b_dev = conf->disks[i].dev;
			else if (spare && action[i] == WRITE+1)
				bh->b_dev = spare->dev;
			else skip=1;
			if (!skip) {
				PRINTK("for %ld schedule op %d on disc %d\n", sh->sector, action[i]-1, i);
				atomic_inc(&sh->count);
				bh->b_rdev = bh->b_dev;
				bh->b_rsector = bh->b_blocknr * (bh->b_size>>9);
				generic_make_request(action[i]-1, bh);
			} else {
				PRINTK("skip op %d on disc %d for sector %ld\n", action[i]-1, i, sh->sector);
				clear_bit(BH_Lock, &bh->b_state);
				set_bit(STRIPE_HANDLE, &sh->state);
			}
		}
}

static inline void raid5_activate_delayed(raid5_conf_t *conf)
{
	if (atomic_read(&conf->preread_active_stripes) < IO_THRESHOLD) {
		while (!list_empty(&conf->delayed_list)) {
			struct list_head *l = conf->delayed_list.next;
			struct stripe_head *sh;
			sh = list_entry(l, struct stripe_head, lru);
			list_del_init(l);
			clear_bit(STRIPE_DELAYED, &sh->state);
			if (!test_and_set_bit(STRIPE_PREREAD_ACTIVE, &sh->state))
				atomic_inc(&conf->preread_active_stripes);
			list_add_tail(&sh->lru, &conf->handle_list);
		}
	}
}
static void raid5_unplug_device(void *data)
{
	raid5_conf_t *conf = (raid5_conf_t *)data;
	unsigned long flags;

	spin_lock_irqsave(&conf->device_lock, flags);

	raid5_activate_delayed(conf);
	
	conf->plugged = 0;
	md_wakeup_thread(conf->thread);

	spin_unlock_irqrestore(&conf->device_lock, flags);
}

static inline void raid5_plug_device(raid5_conf_t *conf)
{
	spin_lock_irq(&conf->device_lock);
	if (list_empty(&conf->delayed_list))
		if (!conf->plugged) {
			conf->plugged = 1;
			queue_task(&conf->plug_tq, &tq_disk);
		}
	spin_unlock_irq(&conf->device_lock);
}

static int raid5_make_request (mddev_t *mddev, int rw, struct buffer_head * bh)
{
	raid5_conf_t *conf = (raid5_conf_t *) mddev->private;
	const unsigned int raid_disks = conf->raid_disks;
	const unsigned int data_disks = raid_disks - 1;
	unsigned int dd_idx, pd_idx;
	unsigned long new_sector;
	int read_ahead = 0;

	struct stripe_head *sh;

	if (rw == READA) {
		rw = READ;
		read_ahead=1;
	}

	new_sector = raid5_compute_sector(bh->b_rsector,
			raid_disks, data_disks, &dd_idx, &pd_idx, conf);

	PRINTK("raid5_make_request, sector %lu\n", new_sector);
	sh = get_active_stripe(conf, new_sector, bh->b_size, read_ahead);
	if (sh) {
		sh->pd_idx = pd_idx;

		add_stripe_bh(sh, bh, dd_idx, rw);

		raid5_plug_device(conf);
		handle_stripe(sh);
		release_stripe(sh);
	} else
		bh->b_end_io(bh, test_bit(BH_Uptodate, &bh->b_state));
	return 0;
}

/*
 * Determine correct block size for this device.
 */
unsigned int device_bsize (kdev_t dev)
{
	unsigned int i, correct_size;

	correct_size = BLOCK_SIZE;
	if (blksize_size[MAJOR(dev)]) {
		i = blksize_size[MAJOR(dev)][MINOR(dev)];
		if (i)
			correct_size = i;
	}

	return correct_size;
}

static int raid5_sync_request (mddev_t *mddev, unsigned long sector_nr)
{
	raid5_conf_t *conf = (raid5_conf_t *) mddev->private;
	struct stripe_head *sh;
	int sectors_per_chunk = conf->chunk_size >> 9;
	unsigned long stripe = sector_nr/sectors_per_chunk;
	int chunk_offset = sector_nr % sectors_per_chunk;
	int dd_idx, pd_idx;
	unsigned long first_sector;
	int raid_disks = conf->raid_disks;
	int data_disks = raid_disks-1;
	int redone = 0;
	int bufsize;

	sh = get_active_stripe(conf, sector_nr, 0, 0);
	bufsize = sh->size;
	redone = sector_nr - sh->sector;
	first_sector = raid5_compute_sector(stripe*data_disks*sectors_per_chunk
		+ chunk_offset, raid_disks, data_disks, &dd_idx, &pd_idx, conf);
	sh->pd_idx = pd_idx;
	spin_lock(&sh->lock);	
	set_bit(STRIPE_SYNCING, &sh->state);
	clear_bit(STRIPE_INSYNC, &sh->state);
	sh->sync_redone = redone;
	spin_unlock(&sh->lock);

	handle_stripe(sh);
	release_stripe(sh);

	return (bufsize>>9)-redone;
}

/*
 * This is our raid5 kernel thread.
 *
 * We scan the hash table for stripes which can be handled now.
 * During the scan, completed stripes are saved for us by the interrupt
 * handler, so that they will not have to wait for our next wakeup.
 */
static void raid5d (void *data)
{
	struct stripe_head *sh;
	raid5_conf_t *conf = data;
	mddev_t *mddev = conf->mddev;
	int handled;

	PRINTK("+++ raid5d active\n");

	handled = 0;

	if (mddev->sb_dirty)
		md_update_sb(mddev);
	md_spin_lock_irq(&conf->device_lock);
	while (1) {
		struct list_head *first;

		if (list_empty(&conf->handle_list) &&
		    atomic_read(&conf->preread_active_stripes) < IO_THRESHOLD &&
		    !conf->plugged &&
		    !list_empty(&conf->delayed_list))
			raid5_activate_delayed(conf);

		if (list_empty(&conf->handle_list))
			break;

		first = conf->handle_list.next;
		sh = list_entry(first, struct stripe_head, lru);

		list_del_init(first);
		atomic_inc(&sh->count);
		if (atomic_read(&sh->count)!= 1)
			BUG();
		md_spin_unlock_irq(&conf->device_lock);
		
		handled++;
		handle_stripe(sh);
		release_stripe(sh);

		md_spin_lock_irq(&conf->device_lock);
	}
	PRINTK("%d stripes handled\n", handled);

	md_spin_unlock_irq(&conf->device_lock);

	PRINTK("--- raid5d inactive\n");
}

/*
 * Private kernel thread for parity reconstruction after an unclean
 * shutdown. Reconstruction on spare drives in case of a failed drive
 * is done by the generic mdsyncd.
 */
static void raid5syncd (void *data)
{
	raid5_conf_t *conf = data;
	mddev_t *mddev = conf->mddev;

	if (!conf->resync_parity)
		return;
	if (conf->resync_parity == 2)
		return;
	down(&mddev->recovery_sem);
	if (md_do_sync(mddev,NULL)) {
		up(&mddev->recovery_sem);
		printk("raid5: resync aborted!\n");
		return;
	}
	conf->resync_parity = 0;
	up(&mddev->recovery_sem);
	printk("raid5: resync finished.\n");
}

static int raid5_run (mddev_t *mddev)
{
	raid5_conf_t *conf;
	int i, j, raid_disk, memory;
	mdp_super_t *sb = mddev->sb;
	mdp_disk_t *desc;
	mdk_rdev_t *rdev;
	struct disk_info *disk;
	struct md_list_head *tmp;
	int start_recovery = 0;

	MOD_INC_USE_COUNT;

	if (sb->level != 5 && sb->level != 4) {
		printk("raid5: md%d: raid level not set to 4/5 (%d)\n", mdidx(mddev), sb->level);
		MOD_DEC_USE_COUNT;
		return -EIO;
	}

	mddev->private = kmalloc (sizeof (raid5_conf_t), GFP_KERNEL);
	if ((conf = mddev->private) == NULL)
		goto abort;
	memset (conf, 0, sizeof (*conf));
	conf->mddev = mddev;

	if ((conf->stripe_hashtbl = (struct stripe_head **) md__get_free_pages(GFP_ATOMIC, HASH_PAGES_ORDER)) == NULL)
		goto abort;
	memset(conf->stripe_hashtbl, 0, HASH_PAGES * PAGE_SIZE);

	conf->device_lock = MD_SPIN_LOCK_UNLOCKED;
	md_init_waitqueue_head(&conf->wait_for_stripe);
	INIT_LIST_HEAD(&conf->handle_list);
	INIT_LIST_HEAD(&conf->delayed_list);
	INIT_LIST_HEAD(&conf->inactive_list);
	atomic_set(&conf->active_stripes, 0);
	atomic_set(&conf->preread_active_stripes, 0);
	conf->buffer_size = PAGE_SIZE; /* good default for rebuild */

	conf->plugged = 0;
	conf->plug_tq.sync = 0;
	conf->plug_tq.routine = &raid5_unplug_device;
	conf->plug_tq.data = conf;

	PRINTK("raid5_run(md%d) called.\n", mdidx(mddev));

	ITERATE_RDEV(mddev,rdev,tmp) {
		/*
		 * This is important -- we are using the descriptor on
		 * the disk only to get a pointer to the descriptor on
		 * the main superblock, which might be more recent.
		 */
		desc = sb->disks + rdev->desc_nr;
		raid_disk = desc->raid_disk;
		disk = conf->disks + raid_disk;

		if (disk_faulty(desc)) {
			printk(KERN_ERR "raid5: disabled device %s (errors detected)\n", partition_name(rdev->dev));
			if (!rdev->faulty) {
				MD_BUG();
				goto abort;
			}
			disk->number = desc->number;
			disk->raid_disk = raid_disk;
			disk->dev = rdev->dev;

			disk->operational = 0;
			disk->write_only = 0;
			disk->spare = 0;
			disk->used_slot = 1;
			continue;
		}
		if (disk_active(desc)) {
			if (!disk_sync(desc)) {
				printk(KERN_ERR "raid5: disabled device %s (not in sync)\n", partition_name(rdev->dev));
				MD_BUG();
				goto abort;
			}
			if (raid_disk > sb->raid_disks) {
				printk(KERN_ERR "raid5: disabled device %s (inconsistent descriptor)\n", partition_name(rdev->dev));
				continue;
			}
			if (disk->operational) {
				printk(KERN_ERR "raid5: disabled device %s (device %d already operational)\n", partition_name(rdev->dev), raid_disk);
				continue;
			}
			printk(KERN_INFO "raid5: device %s operational as raid disk %d\n", partition_name(rdev->dev), raid_disk);
	
			disk->number = desc->number;
			disk->raid_disk = raid_disk;
			disk->dev = rdev->dev;
			disk->operational = 1;
			disk->used_slot = 1;

			conf->working_disks++;
		} else {
			/*
			 * Must be a spare disk ..
			 */
			printk(KERN_INFO "raid5: spare disk %s\n", partition_name(rdev->dev));
			disk->number = desc->number;
			disk->raid_disk = raid_disk;
			disk->dev = rdev->dev;

			disk->operational = 0;
			disk->write_only = 0;
			disk->spare = 1;
			disk->used_slot = 1;
		}
	}

	for (i = 0; i < MD_SB_DISKS; i++) {
		desc = sb->disks + i;
		raid_disk = desc->raid_disk;
		disk = conf->disks + raid_disk;

		if (disk_faulty(desc) && (raid_disk < sb->raid_disks) &&
			!conf->disks[raid_disk].used_slot) {

			disk->number = desc->number;
			disk->raid_disk = raid_disk;
			disk->dev = MKDEV(0,0);

			disk->operational = 0;
			disk->write_only = 0;
			disk->spare = 0;
			disk->used_slot = 1;
		}
	}

	conf->raid_disks = sb->raid_disks;
	/*
	 * 0 for a fully functional array, 1 for a degraded array.
	 */
	conf->failed_disks = conf->raid_disks - conf->working_disks;
	conf->mddev = mddev;
	conf->chunk_size = sb->chunk_size;
	conf->level = sb->level;
	conf->algorithm = sb->layout;
	conf->max_nr_stripes = NR_STRIPES;

#if 0
	for (i = 0; i < conf->raid_disks; i++) {
		if (!conf->disks[i].used_slot) {
			MD_BUG();
			goto abort;
		}
	}
#endif
	if (!conf->chunk_size || conf->chunk_size % 4) {
		printk(KERN_ERR "raid5: invalid chunk size %d for md%d\n", conf->chunk_size, mdidx(mddev));
		goto abort;
	}
	if (conf->algorithm > ALGORITHM_RIGHT_SYMMETRIC) {
		printk(KERN_ERR "raid5: unsupported parity algorithm %d for md%d\n", conf->algorithm, mdidx(mddev));
		goto abort;
	}
	if (conf->failed_disks > 1) {
		printk(KERN_ERR "raid5: not enough operational devices for md%d (%d/%d failed)\n", mdidx(mddev), conf->failed_disks, conf->raid_disks);
		goto abort;
	}

	if (conf->working_disks != sb->raid_disks) {
		printk(KERN_ALERT "raid5: md%d, not all disks are operational -- trying to recover array\n", mdidx(mddev));
		start_recovery = 1;
	}

	{
		const char * name = "raid5d";

		conf->thread = md_register_thread(raid5d, conf, name);
		if (!conf->thread) {
			printk(KERN_ERR "raid5: couldn't allocate thread for md%d\n", mdidx(mddev));
			goto abort;
		}
	}

	memory = conf->max_nr_stripes * (sizeof(struct stripe_head) +
		 conf->raid_disks * ((sizeof(struct buffer_head) + PAGE_SIZE))) / 1024;
	if (grow_stripes(conf, conf->max_nr_stripes, GFP_KERNEL)) {
		printk(KERN_ERR "raid5: couldn't allocate %dkB for buffers\n", memory);
		shrink_stripes(conf, conf->max_nr_stripes);
		goto abort;
	} else
		printk(KERN_INFO "raid5: allocated %dkB for md%d\n", memory, mdidx(mddev));

	/*
	 * Regenerate the "device is in sync with the raid set" bit for
	 * each device.
	 */
	for (i = 0; i < MD_SB_DISKS ; i++) {
		mark_disk_nonsync(sb->disks + i);
		for (j = 0; j < sb->raid_disks; j++) {
			if (!conf->disks[j].operational)
				continue;
			if (sb->disks[i].number == conf->disks[j].number)
				mark_disk_sync(sb->disks + i);
		}
	}
	sb->active_disks = conf->working_disks;

	if (sb->active_disks == sb->raid_disks)
		printk("raid5: raid level %d set md%d active with %d out of %d devices, algorithm %d\n", conf->level, mdidx(mddev), sb->active_disks, sb->raid_disks, conf->algorithm);
	else
		printk(KERN_ALERT "raid5: raid level %d set md%d active with %d out of %d devices, algorithm %d\n", conf->level, mdidx(mddev), sb->active_disks, sb->raid_disks, conf->algorithm);

	if (!start_recovery && !(sb->state & (1 << MD_SB_CLEAN))) {
		const char * name = "raid5syncd";

		conf->resync_thread = md_register_thread(raid5syncd, conf,name);
		if (!conf->resync_thread) {
			printk(KERN_ERR "raid5: couldn't allocate thread for md%d\n", mdidx(mddev));
			goto abort;
		}

		printk("raid5: raid set md%d not clean; reconstructing parity\n", mdidx(mddev));
		conf->resync_parity = 1;
		md_wakeup_thread(conf->resync_thread);
	}

	print_raid5_conf(conf);
	if (start_recovery)
		md_recover_arrays();
	print_raid5_conf(conf);

	/* Ok, everything is just fine now */
	return (0);
abort:
	if (conf) {
		print_raid5_conf(conf);
		if (conf->stripe_hashtbl)
			free_pages((unsigned long) conf->stripe_hashtbl,
							HASH_PAGES_ORDER);
		kfree(conf);
	}
	mddev->private = NULL;
	printk(KERN_ALERT "raid5: failed to run raid set md%d\n", mdidx(mddev));
	MOD_DEC_USE_COUNT;
	return -EIO;
}

static int raid5_stop_resync (mddev_t *mddev)
{
	raid5_conf_t *conf = mddev_to_conf(mddev);
	mdk_thread_t *thread = conf->resync_thread;

	if (thread) {
		if (conf->resync_parity) {
			conf->resync_parity = 2;
			md_interrupt_thread(thread);
			printk(KERN_INFO "raid5: parity resync was not fully finished, restarting next time.\n");
			return 1;
		}
		return 0;
	}
	return 0;
}

static int raid5_restart_resync (mddev_t *mddev)
{
	raid5_conf_t *conf = mddev_to_conf(mddev);

	if (conf->resync_parity) {
		if (!conf->resync_thread) {
			MD_BUG();
			return 0;
		}
		printk("raid5: waking up raid5resync.\n");
		conf->resync_parity = 1;
		md_wakeup_thread(conf->resync_thread);
		return 1;
	} else
		printk("raid5: no restart-resync needed.\n");
	return 0;
}


static int raid5_stop (mddev_t *mddev)
{
	raid5_conf_t *conf = (raid5_conf_t *) mddev->private;

	if (conf->resync_thread)
		md_unregister_thread(conf->resync_thread);
	md_unregister_thread(conf->thread);
	shrink_stripes(conf, conf->max_nr_stripes);
	free_pages((unsigned long) conf->stripe_hashtbl, HASH_PAGES_ORDER);
	kfree(conf);
	mddev->private = NULL;
	MOD_DEC_USE_COUNT;
	return 0;
}

#if RAID5_DEBUG
static void print_sh (struct stripe_head *sh)
{
	int i;

	printk("sh %lu, size %d, pd_idx %d, state %ld.\n", sh->sector, sh->size, sh->pd_idx, sh->state);
	printk("sh %lu,  count %d.\n", sh->sector, atomic_read(&sh->count));
	printk("sh %lu, ", sh->sector);
	for (i = 0; i < MD_SB_DISKS; i++) {
		if (sh->bh_cache[i])
			printk("(cache%d: %p %ld) ", i, sh->bh_cache[i], sh->bh_cache[i]->b_state);
	}
	printk("\n");
}

static void printall (raid5_conf_t *conf)
{
	struct stripe_head *sh;
	int i;

	md_spin_lock_irq(&conf->device_lock);
	for (i = 0; i < NR_HASH; i++) {
		sh = conf->stripe_hashtbl[i];
		for (; sh; sh = sh->hash_next) {
			if (sh->raid_conf != conf)
				continue;
			print_sh(sh);
		}
	}
	md_spin_unlock_irq(&conf->device_lock);

	PRINTK("--- raid5d inactive\n");
}
#endif

static void raid5_status (struct seq_file *seq, mddev_t *mddev)
{
	raid5_conf_t *conf = (raid5_conf_t *) mddev->private;
	mdp_super_t *sb = mddev->sb;
	int i;

	seq_printf (seq, " level %d, %dk chunk, algorithm %d", sb->level, sb->chunk_size >> 10, sb->layout);
	seq_printf (seq, " [%d/%d] [", conf->raid_disks, conf->working_disks);
	for (i = 0; i < conf->raid_disks; i++)
		seq_printf (seq, "%s", conf->disks[i].operational ? "U" : "_");
	seq_printf (seq, "]");
#if RAID5_DEBUG
#define D(x) \
	seq_printf (seq, "<"#x":%d>", atomic_read(&conf->x))
	printall(conf);
#endif

}

static void print_raid5_conf (raid5_conf_t *conf)
{
	int i;
	struct disk_info *tmp;

	printk("RAID5 conf printout:\n");
	if (!conf) {
		printk("(conf==NULL)\n");
		return;
	}
	printk(" --- rd:%d wd:%d fd:%d\n", conf->raid_disks,
		 conf->working_disks, conf->failed_disks);

#if RAID5_DEBUG
	for (i = 0; i < MD_SB_DISKS; i++) {
#else
	for (i = 0; i < conf->working_disks+conf->failed_disks; i++) {
#endif
		tmp = conf->disks + i;
		printk(" disk %d, s:%d, o:%d, n:%d rd:%d us:%d dev:%s\n",
			i, tmp->spare,tmp->operational,
			tmp->number,tmp->raid_disk,tmp->used_slot,
			partition_name(tmp->dev));
	}
}

static int raid5_diskop(mddev_t *mddev, mdp_disk_t **d, int state)
{
	int err = 0;
	int i, failed_disk=-1, spare_disk=-1, removed_disk=-1, added_disk=-1;
	raid5_conf_t *conf = mddev->private;
	struct disk_info *tmp, *sdisk, *fdisk, *rdisk, *adisk;
	mdp_super_t *sb = mddev->sb;
	mdp_disk_t *failed_desc, *spare_desc, *added_desc;
	mdk_rdev_t *spare_rdev, *failed_rdev;

	print_raid5_conf(conf);
	md_spin_lock_irq(&conf->device_lock);
	/*
	 * find the disk ...
	 */
	switch (state) {

	case DISKOP_SPARE_ACTIVE:

		/*
		 * Find the failed disk within the RAID5 configuration ...
		 * (this can only be in the first conf->raid_disks part)
		 */
		for (i = 0; i < conf->raid_disks; i++) {
			tmp = conf->disks + i;
			if ((!tmp->operational && !tmp->spare) ||
					!tmp->used_slot) {
				failed_disk = i;
				break;
			}
		}
		/*
		 * When we activate a spare disk we _must_ have a disk in
		 * the lower (active) part of the array to replace.
		 */
		if ((failed_disk == -1) || (failed_disk >= conf->raid_disks)) {
			MD_BUG();
			err = 1;
			goto abort;
		}
		/* fall through */

	case DISKOP_SPARE_WRITE:
	case DISKOP_SPARE_INACTIVE:

		/*
		 * Find the spare disk ... (can only be in the 'high'
		 * area of the array)
		 */
		for (i = conf->raid_disks; i < MD_SB_DISKS; i++) {
			tmp = conf->disks + i;
			if (tmp->spare && tmp->number == (*d)->number) {
				spare_disk = i;
				break;
			}
		}
		if (spare_disk == -1) {
			MD_BUG();
			err = 1;
			goto abort;
		}
		break;

	case DISKOP_HOT_REMOVE_DISK:

		for (i = 0; i < MD_SB_DISKS; i++) {
			tmp = conf->disks + i;
			if (tmp->used_slot && (tmp->number == (*d)->number)) {
				if (tmp->operational) {
					err = -EBUSY;
					goto abort;
				}
				removed_disk = i;
				break;
			}
		}
		if (removed_disk == -1) {
			MD_BUG();
			err = 1;
			goto abort;
		}
		break;

	case DISKOP_HOT_ADD_DISK:

		for (i = conf->raid_disks; i < MD_SB_DISKS; i++) {
			tmp = conf->disks + i;
			if (!tmp->used_slot) {
				added_disk = i;
				break;
			}
		}
		if (added_disk == -1) {
			MD_BUG();
			err = 1;
			goto abort;
		}
		break;
	}

	switch (state) {
	/*
	 * Switch the spare disk to write-only mode:
	 */
	case DISKOP_SPARE_WRITE:
		if (conf->spare) {
			MD_BUG();
			err = 1;
			goto abort;
		}
		sdisk = conf->disks + spare_disk;
		sdisk->operational = 1;
		sdisk->write_only = 1;
		conf->spare = sdisk;
		break;
	/*
	 * Deactivate a spare disk:
	 */
	case DISKOP_SPARE_INACTIVE:
		sdisk = conf->disks + spare_disk;
		sdisk->operational = 0;
		sdisk->write_only = 0;
		/*
		 * Was the spare being resynced?
		 */
		if (conf->spare == sdisk)
			conf->spare = NULL;
		break;
	/*
	 * Activate (mark read-write) the (now sync) spare disk,
	 * which means we switch it's 'raid position' (->raid_disk)
	 * with the failed disk. (only the first 'conf->raid_disks'
	 * slots are used for 'real' disks and we must preserve this
	 * property)
	 */
	case DISKOP_SPARE_ACTIVE:
		if (!conf->spare) {
			MD_BUG();
			err = 1;
			goto abort;
		}
		sdisk = conf->disks + spare_disk;
		fdisk = conf->disks + failed_disk;

		spare_desc = &sb->disks[sdisk->number];
		failed_desc = &sb->disks[fdisk->number];

		if (spare_desc != *d) {
			MD_BUG();
			err = 1;
			goto abort;
		}

		if (spare_desc->raid_disk != sdisk->raid_disk) {
			MD_BUG();
			err = 1;
			goto abort;
		}
			
		if (sdisk->raid_disk != spare_disk) {
			MD_BUG();
			err = 1;
			goto abort;
		}

		if (failed_desc->raid_disk != fdisk->raid_disk) {
			MD_BUG();
			err = 1;
			goto abort;
		}

		if (fdisk->raid_disk != failed_disk) {
			MD_BUG();
			err = 1;
			goto abort;
		}

		/*
		 * do the switch finally
		 */
		spare_rdev = find_rdev_nr(mddev, spare_desc->number);
		failed_rdev = find_rdev_nr(mddev, failed_desc->number);

		/* There must be a spare_rdev, but there may not be a
		 * failed_rdev.  That slot might be empty...
		 */
		spare_rdev->desc_nr = failed_desc->number;
		if (failed_rdev)
			failed_rdev->desc_nr = spare_desc->number;
		
		xchg_values(*spare_desc, *failed_desc);
		xchg_values(*fdisk, *sdisk);

		/*
		 * (careful, 'failed' and 'spare' are switched from now on)
		 *
		 * we want to preserve linear numbering and we want to
		 * give the proper raid_disk number to the now activated
		 * disk. (this means we switch back these values)
		 */
	
		xchg_values(spare_desc->raid_disk, failed_desc->raid_disk);
		xchg_values(sdisk->raid_disk, fdisk->raid_disk);
		xchg_values(spare_desc->number, failed_desc->number);
		xchg_values(sdisk->number, fdisk->number);

		*d = failed_desc;

		if (sdisk->dev == MKDEV(0,0))
			sdisk->used_slot = 0;

		/*
		 * this really activates the spare.
		 */
		fdisk->spare = 0;
		fdisk->write_only = 0;

		/*
		 * if we activate a spare, we definitely replace a
		 * non-operational disk slot in the 'low' area of
		 * the disk array.
		 */
		conf->failed_disks--;
		conf->working_disks++;
		conf->spare = NULL;

		break;

	case DISKOP_HOT_REMOVE_DISK:
		rdisk = conf->disks + removed_disk;

		if (rdisk->spare && (removed_disk < conf->raid_disks)) {
			MD_BUG();	
			err = 1;
			goto abort;
		}
		rdisk->dev = MKDEV(0,0);
		rdisk->used_slot = 0;

		break;

	case DISKOP_HOT_ADD_DISK:
		adisk = conf->disks + added_disk;
		added_desc = *d;

		if (added_disk != added_desc->number) {
			MD_BUG();	
			err = 1;
			goto abort;
		}

		adisk->number = added_desc->number;
		adisk->raid_disk = added_desc->raid_disk;
		adisk->dev = MKDEV(added_desc->major,added_desc->minor);

		adisk->operational = 0;
		adisk->write_only = 0;
		adisk->spare = 1;
		adisk->used_slot = 1;


		break;

	default:
		MD_BUG();	
		err = 1;
		goto abort;
	}
abort:
	md_spin_unlock_irq(&conf->device_lock);
	print_raid5_conf(conf);
	return err;
}

static mdk_personality_t raid5_personality=
{
	name:		"raid5",
	make_request:	raid5_make_request,
	run:		raid5_run,
	stop:		raid5_stop,
	status:		raid5_status,
	error_handler:	raid5_error,
	diskop:		raid5_diskop,
	stop_resync:	raid5_stop_resync,
	restart_resync:	raid5_restart_resync,
	sync_request:	raid5_sync_request
};

static int md__init raid5_init (void)
{
	return register_md_personality (RAID5, &raid5_personality);
}

static void raid5_exit (void)
{
	unregister_md_personality (RAID5);
}

module_init(raid5_init);
module_exit(raid5_exit);
MODULE_LICENSE("GPL");