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