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