1/*
2 * CDDL HEADER START
3 *
4 * The contents of this file are subject to the terms of the
5 * Common Development and Distribution License (the "License").
6 * You may not use this file except in compliance with the License.
7 *
8 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
9 * or http://www.opensolaris.org/os/licensing.
10 * See the License for the specific language governing permissions
11 * and limitations under the License.
12 *
13 * When distributing Covered Code, include this CDDL HEADER in each
14 * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
15 * If applicable, add the following below this CDDL HEADER, with the
16 * fields enclosed by brackets "[]" replaced with your own identifying
17 * information: Portions Copyright [yyyy] [name of copyright owner]
18 *
19 * CDDL HEADER END
20 */
21/*
22 * Copyright 2008 Sun Microsystems, Inc.  All rights reserved.
23 * Use is subject to license terms.
24 *
25 * copyright (c) 1990, 1991 UNIX System Laboratories, Inc.
26 * copyright (c) 1984, 1986, 1987, 1988, 1989, 1990 AT&T
27 * All rights reserved.
28 */
29
30/*
31 * Copyrighted as an unpublished work.
32 * (c) Copyright INTERACTIVE Systems Corporation 1986, 1988, 1990
33 * All rights reserved.
34 */
35
36#include <sys/types.h>
37#include <ctype.h>
38#include <fcntl.h>
39#include <malloc.h>
40#include <sys/stat.h>
41#include <sys/swap.h>
42#include <stdio.h>
43#include <string.h>
44#include <sys/vtoc.h>
45#include <sys/param.h>
46#include <sys/dkio.h>
47#include <sys/dktp/altsctr.h>
48#include <sys/dktp/fdisk.h>
49#include "badsec.h"
50#include "global.h"
51#include "ctlr_ata.h"
52#include "misc.h"
53
54#define	FAILURE	1
55#define	SUCCESS	0
56
57#define	CMD_READ	0
58#define	CMD_WRITE	1
59
60struct	badsec_lst *badsl_chain = NULL;
61int	badsl_chain_cnt = 0;
62struct	badsec_lst *gbadsl_chain = NULL;
63int	gbadsl_chain_cnt = 0;
64
65static struct	alts_mempart alts_part = { 0, NULL, 0 };
66struct	alts_mempart	*ap = &alts_part;	/* pointer to incore */
67						/*  alts tables	*/
68
69/* prototypes */
70int updatebadsec(struct  dkl_partition *, int);
71int read_altsctr(struct  dkl_partition *);
72static int chk_badsec();
73static int init_altsctr();
74static int get_altsctr();
75int wr_altsctr();
76static void get_badsec();
77static int count_badsec();
78static int gen_alts_ent();
79static int assign_altsctr();
80static void expand_map();
81static void compress_map();
82static int altsmap_getbit(blkaddr_t);
83static blkaddr_t altsmap_alloc(blkaddr_t, blkaddr_t, int, int);
84static void ent_sort(struct  alts_ent *, int);
85static void ent_compress(struct  alts_ent *, int);
86static int ent_merge(struct alts_ent *, struct alts_ent *, int,
87		struct alts_ent *, int);
88static int ent_bsearch(struct  alts_ent *, int, struct  alts_ent *);
89static int chk_bad_altsctr(blkaddr_t);
90
91/*
92 * updatebadsec () -- update bad sector/track mapping tables
93 */
94int
95updatebadsec(part, init_flag)
96int	init_flag;
97struct  dkl_partition *part;
98{
99	if (init_flag)
100		ap->ap_flag |= ALTS_ADDPART;
101	get_badsec();
102	(void) read_altsctr(part);
103	ent_sort(ap->ap_gbadp, ap->ap_gbadcnt);
104	ent_compress(ap->ap_gbadp, ap->ap_gbadcnt);
105	(void) gen_alts_ent();
106	compress_map();
107	return (SUCCESS);
108}
109
110/*
111 * read_altsctr( ptr to alternate sector partition )
112 *		-- read the alternate sector partition tables
113 */
114int
115read_altsctr(struct dkl_partition *part)
116{
117	if (ap->ap_tblp == NULL) {
118/*	    allocate buffer for the alts partition table (sector size)	*/
119	    ap->ap_tbl_secsiz = byte_to_secsiz(ALTS_PARTTBL_SIZE, NBPSCTR);
120	    ap->ap_tblp = (struct alts_parttbl *)malloc(ap->ap_tbl_secsiz);
121	    if (ap->ap_tblp == NULL) {
122		(void) fprintf(stderr,
123			"Unable to malloc alternate partition table.\n");
124		return (50);
125	    }
126
127/*	    allocate buffer for the alts partition map (sector size)	*/
128/*	    buffers include the disk image bit map			*/
129/*	    and the incore transformed char map				*/
130
131	    if ((ap->ap_memmapp = (uchar_t *)malloc(part->p_size)) == NULL) {
132		(void) fprintf(stderr,
133			"Unable to malloc incore alternate partition map.\n");
134		return (51);
135	    }
136	    ap->ap_tblp->alts_map_len = (part->p_size + 8 - 1) / 8;
137	    ap->ap_map_secsiz = byte_to_secsiz(ap->ap_tblp->alts_map_len,
138						NBPSCTR);
139	    ap->ap_map_sectot = ap->ap_map_secsiz / NBPSCTR;
140	    if ((ap->ap_mapp = (uchar_t *)malloc(ap->ap_map_secsiz)) == NULL) {
141		(void) fprintf(stderr,
142				"Unable to malloc alternate partition map.\n");
143		return (52);
144	    }
145/*	    clear the buffers to zero					*/
146	    (void) memset(ap->ap_memmapp, 0, part->p_size);
147	    (void) memset(ap->ap_mapp, 0, ap->ap_map_secsiz);
148	    ap->part = *part;		/* struct copy			*/
149
150/*
151 *	    if add alternate partition flag is set, then install the partition
152 *	    otherwise read the alts partition info from disk
153 *	    if failed, then assume the first installation
154 */
155	    if (ap->ap_flag & ALTS_ADDPART)
156	    {
157		(void) fprintf(stderr,
158			"WARNING: Manually initializing alternate table.\n");
159		(void) init_altsctr();
160	    } else {
161		if (get_altsctr() == SUCCESS)
162		    (void) chk_badsec();
163		else
164		    (void) init_altsctr();
165	    }
166	}
167	return (SUCCESS);
168}
169
170
171/*
172 *	checking duplicate bad sectors or bad sectors in ALTSCTR partition
173 */
174static int
175chk_badsec()
176{
177	blkaddr_t	badsec;
178	blkaddr_t	altsp_srtsec = ap->part.p_start;
179	blkaddr_t	altsp_endsec = ap->part.p_start + ap->part.p_size - 1;
180	int	cnt;
181	int	status;
182
183	for (cnt = 0; cnt < ap->ap_gbadcnt; cnt++) {
184	    badsec = (ap->ap_gbadp)[cnt].bad_start;
185
186	    /* if bad sector is within the ATLSCTR partition */
187	    if ((badsec >= altsp_srtsec) && (badsec <= altsp_endsec)) {
188		if ((ap->ap_memmapp)[badsec - altsp_srtsec] != ALTS_BAD) {
189		    if ((badsec >= altsp_srtsec) && (badsec <= (altsp_srtsec +
190			ap->ap_tbl_secsiz / NBPSCTR - 1))) {
191			(void) fprintf(stderr,
192			"Alternate partition information table is bad.\n");
193			return (53);
194		    }
195		    if ((badsec >= altsp_srtsec+ap->ap_tblp->alts_map_base) &&
196			(badsec <= (altsp_srtsec + ap->ap_tblp->alts_map_base +
197			ap->ap_map_sectot - 1))) {
198			(void) fprintf(stderr,
199					"Alternate partition map is bad.\n");
200			return (54);
201		    }
202		    if ((badsec >= altsp_srtsec+ap->ap_tblp->alts_ent_base) &&
203			(badsec <= (altsp_srtsec + ap->ap_tblp->alts_ent_base +
204			ap->ap_ent_secsiz / NBPSCTR - 1))) {
205			(void) fprintf(stderr,
206				"Alternate partition entry table is bad.\n");
207			return (55);
208		    }
209		    (ap->ap_memmapp)[badsec - altsp_srtsec] = ALTS_BAD;
210		    (ap->ap_gbadp)[cnt].bad_start = (uint32_t)ALTS_ENT_EMPTY;
211		} else {
212		    status = chk_bad_altsctr(badsec);
213		    (ap->ap_gbadp)[cnt].bad_start = (uint32_t)ALTS_ENT_EMPTY;
214		}
215	    } else {
216/*
217 *		binary search for bad sector in the alts entry table
218 */
219		status = ent_bsearch(ap->ap_entp, ap->ap_tblp->alts_ent_used,
220					&((ap->ap_gbadp)[cnt]));
221/*
222 *		if the bad sector had already been remapped(found in alts_entry)
223 *		then ignore the bad sector
224 */
225		if (status != -1) {
226		    (ap->ap_gbadp)[cnt].bad_start = (uint32_t)ALTS_ENT_EMPTY;
227		}
228	    }
229	}
230	return (SUCCESS);
231}
232
233/*
234 *	initialize the alternate partition tables
235 */
236static int
237init_altsctr()
238{
239	blkaddr_t	badsec;
240	blkaddr_t	altsp_srtsec = ap->part.p_start;
241	blkaddr_t	altsp_endsec = ap->part.p_start + ap->part.p_size - 1;
242	int	cnt;
243
244	ap->ap_entp = NULL;
245	ap->ap_ent_secsiz = 0;
246	ap->ap_tblp->alts_sanity = ALTS_SANITY;
247	ap->ap_tblp->alts_version = ALTS_VERSION1;
248	ap->ap_tblp->alts_map_len = (ap->part.p_size + 8 - 1) / 8;
249	ap->ap_tblp->alts_ent_used = 0;
250	ap->ap_tblp->alts_ent_base = 0;
251	ap->ap_tblp->alts_ent_end  = 0;
252	ap->ap_tblp->alts_resv_base = ap->part.p_size - 1;
253	for (cnt = 0; cnt < 5; cnt++)
254	    ap->ap_tblp->alts_pad[cnt] = 0;
255
256	for (cnt = 0; cnt < ap->ap_gbadcnt; cnt++) {
257	    badsec = (ap->ap_gbadp)[cnt].bad_start;
258	    if ((badsec >= altsp_srtsec) && (badsec <= altsp_endsec)) {
259		if (badsec == altsp_srtsec) {
260		    (void) fprintf(stderr,
261			"First sector of alternate partition is bad.\n");
262		    return (56);
263		}
264		(ap->ap_memmapp)[badsec - altsp_srtsec] = ALTS_BAD;
265		(ap->ap_gbadp)[cnt].bad_start = (uint32_t)ALTS_ENT_EMPTY;
266	    }
267	}
268
269/*	allocate the alts_map on disk skipping possible bad sectors	*/
270	ap->ap_tblp->alts_map_base =
271		altsmap_alloc(ap->ap_tbl_secsiz / NBPSCTR,
272			ap->part.p_size, ap->ap_map_sectot, ALTS_MAP_UP);
273	if (ap->ap_tblp->alts_map_base == 0) {
274	    perror("Unable to allocate alternate map on disk: ");
275	    return (57);
276	}
277	(void) wr_altsctr();
278
279	return (SUCCESS);
280}
281
282
283/*
284 *	read the alternate partition tables from disk
285 */
286static int
287get_altsctr(void)
288{
289	int	mystatus = FAILURE;
290	int	status = 0;
291
292/*	get alts partition table info					*/
293
294	status = ata_rdwr(DIR_READ, cur_file, altsec_offset,
295			ap->ap_tbl_secsiz / UBSIZE, (char *)ap->ap_tblp,
296			0, NULL);
297	if (status == FAILURE) {
298	    perror("Unable to read alternate sector partition: ");
299	    return (58);
300	}
301	if (ap->ap_tblp->alts_sanity != ALTS_SANITY)
302	    return (mystatus);
303
304/*	get the alts map						*/
305	status = ata_rdwr(DIR_READ, cur_file,
306		(ap->ap_tblp->alts_map_base) + altsec_offset,
307		ap->ap_map_secsiz / UBSIZE, (char *)ap->ap_mapp, 0, NULL);
308	if (status == FAILURE) {
309	    perror("Unable to read alternate sector partition map: ");
310	    return (59);
311	}
312
313/*	transform the disk image bit-map to incore char map		*/
314	expand_map();
315
316	if (ap->ap_tblp->alts_ent_used == 0) {
317	    ap->ap_entp = NULL;
318	    ap->ap_ent_secsiz = 0;
319	} else {
320	    ap->ap_ent_secsiz = byte_to_secsiz(
321			(ap->ap_tblp->alts_ent_used*ALTS_ENT_SIZE), NBPSCTR);
322	    if ((ap->ap_entp =
323		(struct alts_ent *)malloc(ap->ap_ent_secsiz)) == NULL) {
324		(void) fprintf(stderr,
325			"Unable to malloc alternate sector entry table.\n");
326		return (60);
327	    }
328
329	status = ata_rdwr(DIR_READ, cur_file,
330			(ap->ap_tblp->alts_ent_base) + altsec_offset,
331			ap->ap_ent_secsiz / UBSIZE, (char *)ap->ap_entp,
332			0, NULL);
333	if (status == FAILURE) {
334		perror("Unable to read alternate sector entry table: ");
335		return (61);
336	    }
337	}
338
339	return (SUCCESS);
340}
341
342
343/*
344 *	update the new alternate partition tables on disk
345 */
346int
347wr_altsctr()
348{
349	int	status;
350
351	if (ap->ap_tblp == NULL)
352		return (0);
353	status = ata_rdwr(DIR_WRITE, cur_file, altsec_offset,
354	    ap->ap_tbl_secsiz / UBSIZE, (char *)ap->ap_tblp, 0, NULL);
355	if (status) {
356		(void) printf("ata_rdwr status = %d need = %d\n",
357		    status, ap->ap_tbl_secsiz / 512);
358		perror("Unable to write with ata_rdwr the alt sector part: ");
359		return (62);
360	}
361
362	if (ata_rdwr(DIR_WRITE, cur_file, (ap->ap_tblp->alts_map_base) +
363			altsec_offset, ap->ap_map_secsiz / UBSIZE,
364			(char *)ap->ap_mapp, 0, NULL) == FAILURE) {
365	    perror("Unable to write alternate sector partition map: ");
366	    return (63);
367	}
368
369	if (ap->ap_tblp->alts_ent_used != 0) {
370	    if (ata_rdwr(DIR_WRITE, cur_file,
371				(ap->ap_tblp->alts_ent_base)+ altsec_offset,
372				ap->ap_ent_secsiz / UBSIZE,
373				(char *)ap->ap_entp, 0, NULL) == FAILURE) {
374		perror("Unable to write alternate sector entry table: ");
375		return (64);
376	    }
377	}
378	return (0);
379}
380
381
382/*
383 *	get a list of bad sector
384 */
385static void
386get_badsec()
387{
388	int	cnt;
389	struct	badsec_lst *blc_p;
390	blkaddr_t	curbad;
391	blkaddr_t	maxsec = cur_dtype->dtype_nhead *
392				cur_dtype->dtype_ncyl *
393				cur_dtype->dtype_nsect;
394	struct	alts_ent *growbadp;
395	int	i;
396
397	cnt = count_badsec();
398	if (!cnt) {
399	    ap->ap_gbadp = NULL;
400	    ap->ap_gbadcnt = 0;
401	} else {
402	    ap->ap_gbadp = malloc(cnt*ALTS_ENT_SIZE);
403	    if (ap->ap_gbadp == NULL) {
404		    err_print("get_badsec: unable to malloc %d bytes\n",
405			cnt*ALTS_ENT_SIZE);
406		    fullabort();
407	    }
408	    (void) memset(ap->ap_gbadp, 0, cnt*ALTS_ENT_SIZE);
409
410	    for (growbadp = ap->ap_gbadp, cnt = 0, blc_p = badsl_chain;
411		blc_p; blc_p = blc_p->bl_nxt) {
412		for (i = 0; i < blc_p->bl_cnt; i++) {
413		    curbad = blc_p->bl_sec[i];
414		    if (curbad < (blkaddr_t)cur_dtype->dtype_nsect) {
415			(void) fprintf(stderr,
416"Ignoring bad sector %ld which is in first track of the drive.\n", curbad);
417			continue;
418		    }
419		    if (curbad >= maxsec) {
420			(void) fprintf(stderr,
421"Ignoring bad sector %ld which is past the end of the drive.\n", curbad);
422			continue;
423		    }
424		    growbadp[cnt].bad_start = curbad;
425		    growbadp[cnt].bad_end = curbad;
426		    cnt++;
427		}
428	    }
429	}
430	ap->ap_gbadcnt = cnt;
431}
432
433/*
434 *	count number of bad sector on list
435 *	merging the bad sector list from surface analysis and the
436 *	one given through the command line
437 */
438static int
439count_badsec()
440{
441
442	struct badsec_lst *blc_p;
443
444	if (!badsl_chain)
445		badsl_chain = gbadsl_chain;
446	else {
447		for (blc_p = badsl_chain; blc_p->bl_nxt; blc_p = blc_p->bl_nxt)
448			;
449		blc_p->bl_nxt = gbadsl_chain;
450	}
451
452	badsl_chain_cnt += gbadsl_chain_cnt;
453	return (badsl_chain_cnt);
454}
455
456
457/*
458 *	generate alternate entry table by merging the existing and
459 *	the new entry list.
460 */
461static int
462gen_alts_ent() {
463	uint_t	ent_used;
464	struct	alts_ent *entp;
465
466	if (ap->ap_gbadcnt == 0)
467	    return (0);
468
469	ent_used = ap->ap_tblp->alts_ent_used + ap->ap_gbadcnt;
470	ap->ap_ent_secsiz = byte_to_secsiz(ent_used*ALTS_ENT_SIZE, NBPSCTR);
471	entp = malloc(ap->ap_ent_secsiz);
472	if (entp == NULL) {
473		err_print("get_alts_ent: unable to malloc %d bytes\n",
474		    ap->ap_ent_secsiz);
475		fullabort();
476	}
477
478	ent_used = ent_merge(entp, ap->ap_entp, ap->ap_tblp->alts_ent_used,
479			    ap->ap_gbadp, ap->ap_gbadcnt);
480	if (ap->ap_entp)
481	    free(ap->ap_entp);
482	if (ap->ap_gbadp)
483	    free(ap->ap_gbadp);
484	ap->ap_entp = entp;
485	ap->ap_ent_secsiz = byte_to_secsiz(ent_used*ALTS_ENT_SIZE, NBPSCTR);
486	ap->ap_tblp->alts_ent_used = ent_used;
487	ap->ap_gbadp = NULL;
488	ap->ap_gbadcnt = 0;
489
490/*	assign alternate sectors to the bad sectors			*/
491	(void) assign_altsctr();
492
493/*	allocate the alts_entry on disk skipping possible bad sectors	*/
494	ap->ap_tblp->alts_ent_base =
495		altsmap_alloc((blkaddr_t)ap->ap_tblp->alts_map_base +
496			ap->ap_map_sectot, (blkaddr_t)ap->part.p_size,
497			ap->ap_ent_secsiz / NBPSCTR, ALTS_MAP_UP);
498	if (ap->ap_tblp->alts_ent_base == 0) {
499	    perror("Unable to allocate alternate entry table on disk: ");
500	    return (65);
501	}
502
503	ap->ap_tblp->alts_ent_end = ap->ap_tblp->alts_ent_base +
504			(ap->ap_ent_secsiz / NBPSCTR) - 1;
505	return (0);
506}
507
508
509/*
510 *	assign alternate sectors for bad sector mapping
511 */
512static int
513assign_altsctr()
514{
515	uint_t	i;
516	uint_t	j;
517	blkaddr_t	alts_ind;
518	uint_t	cluster;
519
520	for (i = 0; i < ap->ap_tblp->alts_ent_used; i++) {
521	    if ((ap->ap_entp)[i].bad_start == (uint32_t)ALTS_ENT_EMPTY)
522		continue;
523	    if ((ap->ap_entp)[i].good_start != 0)
524		continue;
525	    cluster = (ap->ap_entp)[i].bad_end-(ap->ap_entp)[i].bad_start +1;
526	    alts_ind =
527		altsmap_alloc(ap->part.p_size-1, ap->ap_tblp->alts_map_base +
528			ap->ap_map_sectot - 1, cluster, ALTS_MAP_DOWN);
529	    if (alts_ind == 0) {
530		(void) fprintf(stderr,
531	"Unable to allocate alternates for bad starting sector %u.\n",
532			(ap->ap_entp)[i].bad_start);
533		return (65);
534	    }
535	    alts_ind = alts_ind - cluster + 1;
536	    (ap->ap_entp)[i].good_start = alts_ind +ap->part.p_start;
537	    for (j = 0; j < cluster; j++) {
538		(ap->ap_memmapp)[alts_ind+j] = ALTS_BAD;
539	    }
540
541	}
542	return (SUCCESS);
543}
544
545/*
546 *	transform the disk image alts bit map to incore char map
547 */
548static void
549expand_map(void)
550{
551	int	i;
552
553	for (i = 0; i < ap->part.p_size; i++) {
554	    (ap->ap_memmapp)[i] = altsmap_getbit(i);
555	}
556}
557
558/*
559 *	transform the incore alts char map to the disk image bit map
560 */
561static void
562compress_map(void)
563{
564	int	i;
565	int	bytesz;
566	char	mask = 0;
567	int	maplen = 0;
568
569	for (i = 0, bytesz = 7; i < ap->part.p_size; i++) {
570	    mask |= ((ap->ap_memmapp)[i] << bytesz--);
571	    if (bytesz < 0) {
572		(ap->ap_mapp)[maplen++] = mask;
573		bytesz = 7;
574		mask = 0;
575	    }
576	}
577/*
578 *	if partition size != multiple number of bytes
579 *	then record the last partial byte
580 */
581	if (bytesz != 7)
582	    (ap->ap_mapp)[maplen] = mask;
583
584}
585
586/*
587 *	given a bad sector number, search in the alts bit map
588 *	and identify the sector as good or bad
589 */
590static int
591altsmap_getbit(badsec)
592blkaddr_t	badsec;
593{
594	uint_t	slot = badsec / 8;
595	uint_t	field = badsec % 8;
596	uchar_t	mask;
597
598	mask = ALTS_BAD<<7;
599	mask >>= field;
600	if ((ap->ap_mapp)[slot] & mask)
601	    return (ALTS_BAD);
602	return (ALTS_GOOD);
603}
604
605
606/*
607 *	allocate a range of sectors from the alternate partition
608 */
609static blkaddr_t
610altsmap_alloc(srt_ind, end_ind, cnt, dir)
611blkaddr_t	srt_ind;
612blkaddr_t	end_ind;
613int	cnt;
614int	dir;
615{
616	blkaddr_t	i;
617	blkaddr_t	total;
618	blkaddr_t	first_ind;
619
620	for (i = srt_ind, first_ind = srt_ind, total = 0;
621	    i != end_ind; i += dir) {
622	    if ((ap->ap_memmapp)[i] == ALTS_BAD) {
623		total = 0;
624		first_ind = i + dir;
625		continue;
626	    }
627	    total++;
628	    if (total == cnt)
629		return (first_ind);
630
631	}
632	return (0);
633}
634
635
636
637/*
638 *	bubble sort the entry table into ascending order
639 */
640static void
641ent_sort(buf, cnt)
642struct	alts_ent buf[];
643int	cnt;
644{
645struct	alts_ent temp;
646int	flag;
647int	i, j;
648
649	for (i = 0; i < cnt-1; i++) {
650	    temp = buf[cnt-1];
651	    flag = 1;
652
653	    for (j = cnt-1; j > i; j--) {
654		if (buf[j-1].bad_start < temp.bad_start) {
655		    buf[j] = temp;
656		    temp = buf[j-1];
657		} else {
658		    buf[j] = buf[j-1];
659		    flag = 0;
660		}
661	    }
662	    buf[i] = temp;
663	    if (flag) break;
664	}
665
666}
667
668
669/*
670 *	compress all the contiguous bad sectors into a single entry
671 *	in the entry table. The entry table must be sorted into ascending
672 *	before the compression.
673 */
674static void
675ent_compress(buf, cnt)
676struct	alts_ent buf[];
677int	cnt;
678{
679int	keyp;
680int	movp;
681int	i;
682
683	for (i = 0; i < cnt; i++) {
684	    if (buf[i].bad_start == (uint32_t)ALTS_ENT_EMPTY)
685		continue;
686	    for (keyp = i, movp = i+1; movp < cnt; movp++) {
687		if (buf[movp].bad_start == (uint32_t)ALTS_ENT_EMPTY)
688			continue;
689		if (buf[keyp].bad_end+1 != buf[movp].bad_start)
690		    break;
691		buf[keyp].bad_end++;
692		buf[movp].bad_start = (uint32_t)ALTS_ENT_EMPTY;
693	    }
694	    if (movp == cnt) break;
695	}
696}
697
698
699/*
700 *	merging two entry tables into a single table. In addition,
701 *	all empty slots in the entry table will be removed.
702 */
703static int
704ent_merge(buf, list1, lcnt1, list2, lcnt2)
705struct	alts_ent buf[];
706struct	alts_ent list1[];
707int	lcnt1;
708struct	alts_ent list2[];
709int	lcnt2;
710{
711	int	i;
712	int	j1, j2;
713
714	for (i = 0, j1 = 0, j2 = 0; j1 < lcnt1 && j2 < lcnt2; ) {
715	    if (list1[j1].bad_start == (uint32_t)ALTS_ENT_EMPTY) {
716		j1++;
717		continue;
718	    }
719	    if (list2[j2].bad_start == (uint32_t)ALTS_ENT_EMPTY) {
720		j2++;
721		continue;
722	    }
723	    if (list1[j1].bad_start < list2[j2].bad_start)
724		buf[i++] = list1[j1++];
725	    else
726		buf[i++] = list2[j2++];
727	}
728	for (; j1 < lcnt1; j1++) {
729	    if (list1[j1].bad_start == (uint32_t)ALTS_ENT_EMPTY)
730		continue;
731	    buf[i++] = list1[j1];
732	}
733	for (; j2 < lcnt2; j2++) {
734	    if (list2[j2].bad_start == (uint32_t)ALTS_ENT_EMPTY)
735		continue;
736	    buf[i++] = list2[j2];
737	}
738	return (i);
739}
740
741
742/*
743 *	binary search for bad sector in the alternate entry table
744 */
745static int
746ent_bsearch(buf, cnt, key)
747struct	alts_ent buf[];
748int	cnt;
749struct	alts_ent *key;
750{
751	int	i;
752	int	ind;
753	int	interval;
754	int	mystatus = -1;
755
756	if (!cnt)
757	    return (mystatus);
758
759	for (i = 1; i <= cnt; i <<= 1)
760	    ind = i;
761
762	for (interval = ind; interval; ) {
763	    if ((key->bad_start >= buf[ind-1].bad_start) &&
764		(key->bad_start <= buf[ind-1].bad_end)) {
765		return (mystatus = ind-1);
766	    } else {
767		interval >>= 1;
768		if (!interval) break;
769		if (key->bad_start < buf[ind-1].bad_start) {
770		    ind = ind - interval;
771		} else {
772/*	if key is larger than the last element then break	*/
773		    if (ind == cnt) break;
774		    if ((ind+interval) <= cnt)
775			ind += interval;
776		}
777	    }
778	}
779	return (mystatus);
780}
781
782/*
783 *	check for bad sector in assigned alternate sectors
784 */
785static int
786chk_bad_altsctr(badsec)
787blkaddr_t	badsec;
788{
789	int	i;
790	blkaddr_t	numsec;
791	int	cnt = ap->ap_tblp->alts_ent_used;
792/*
793 *	daddr_t intv[3];
794 */
795
796	for (i = 0; i < cnt; i++) {
797	    numsec = (ap->ap_entp)[i].bad_end - (ap->ap_entp)[i].bad_start;
798	    if ((badsec >= (ap->ap_entp)[i].good_start) &&
799		(badsec <= ((ap->ap_entp)[i].good_start + numsec))) {
800		(void) fprintf(stderr,
801		"Bad sector %ld is an assigned alternate sector.\n", badsec);
802		return (66);
803/*
804 *		if (!numsec) {
805 *		    (ap->ap_entp)[i].good_start = 0;
806 *		    return (FAILURE);
807 *		}
808 *		intv[0] = badsec - (ap->ap_entp)[i].good_start;
809 *		intv[1] = 1;
810 *		intv[2] = (ap->ap_entp)[i].good_start + numsec - badsec;
811 */
812	    }
813	}
814/*	the bad sector has already been identified as bad		*/
815	return (SUCCESS);
816
817}
818