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