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