usr/src/cmd/format/ix_altsctr.c

   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         free(ap->ap_entp);
 482         free(ap->ap_gbadp);
 483         ap->ap_entp = entp;
 484         ap->ap_ent_secsiz = byte_to_secsiz(ent_used*ALTS_ENT_SIZE, NBPSCTR);
 485         ap->ap_tblp->alts_ent_used = ent_used;
 486         ap->ap_gbadp = NULL;
 487         ap->ap_gbadcnt = 0;
 488
 489 /*      assign alternate sectors to the bad sectors                     */
 490         (void) assign_altsctr();
 491
 492 /*      allocate the alts_entry on disk skipping possible bad sectors   */
 493         ap->ap_tblp->alts_ent_base =
 494                 altsmap_alloc((blkaddr_t)ap->ap_tblp->alts_map_base +
 495                         ap->ap_map_sectot, (blkaddr_t)ap->part.p_size,
 496                         ap->ap_ent_secsiz / NBPSCTR, ALTS_MAP_UP);
 497         if (ap->ap_tblp->alts_ent_base == NULL) {
 498             perror("Unable to allocate alternate entry table on disk: ");
 499             return (65);
 500         }
 501
 502         ap->ap_tblp->alts_ent_end = ap->ap_tblp->alts_ent_base +
 503                         (ap->ap_ent_secsiz / NBPSCTR) - 1;
 504         return (0);
 505 }
 506
 507
 508 /*
 509  *      assign alternate sectors for bad sector mapping
 510  */
 511 static int
 512 assign_altsctr()
 513 {
 514         uint_t  i;
 515         uint_t  j;
 516         blkaddr_t       alts_ind;
 517         uint_t  cluster;
 518
 519         for (i = 0; i < ap->ap_tblp->alts_ent_used; i++) {
 520             if ((ap->ap_entp)[i].bad_start == (uint32_t)ALTS_ENT_EMPTY)
 521                 continue;
 522             if ((ap->ap_entp)[i].good_start != 0)
 523                 continue;
 524             cluster = (ap->ap_entp)[i].bad_end-(ap->ap_entp)[i].bad_start +1;
 525             alts_ind =
 526                 altsmap_alloc(ap->part.p_size-1, ap->ap_tblp->alts_map_base +
 527                         ap->ap_map_sectot - 1, cluster, ALTS_MAP_DOWN);
 528             if (alts_ind == NULL) {
 529                 (void) fprintf(stderr,
 530         "Unable to allocate alternates for bad starting sector %u.\n",
 531                         (ap->ap_entp)[i].bad_start);
 532                 return (65);
 533             }
 534             alts_ind = alts_ind - cluster + 1;
 535             (ap->ap_entp)[i].good_start = alts_ind +ap->part.p_start;
 536             for (j = 0; j < cluster; j++) {
 537                 (ap->ap_memmapp)[alts_ind+j] = ALTS_BAD;
 538             }
 539
 540         }
 541         return (SUCCESS);
 542 }
 543
 544 /*
 545  *      transform the disk image alts bit map to incore char map
 546  */
 547 static void
 548 expand_map()
 549 {
 550         int     i;
 551
 552         for (i = 0; i < ap->part.p_size; i++) {
 553             (ap->ap_memmapp)[i] = altsmap_getbit(i);
 554         }
 555 }
 556
 557 /*
 558  *      transform the incore alts char map to the disk image bit map
 559  */
 560 static void
 561 compress_map()
 562 {
 563
 564         int     i;
 565         int     bytesz;
 566         char    mask = 0;
 567         int     maplen = 0;
 568
 569         for (i = 0, bytesz = 7; i < ap->part.p_size; i++) {
 570             mask |= ((ap->ap_memmapp)[i] << bytesz--);
 571             if (bytesz < 0) {
 572                 (ap->ap_mapp)[maplen++] = mask;
 573                 bytesz = 7;
 574                 mask = 0;
 575             }
 576         }
 577 /*
 578  *      if partition size != multiple number of bytes
 579  *      then record the last partial byte
 580  */
 581         if (bytesz != 7)
 582             (ap->ap_mapp)[maplen] = mask;
 583
 584 }
 585
 586 /*
 587  *      given a bad sector number, search in the alts bit map
 588  *      and identify the sector as good or bad
 589  */
 590 static int
 591 altsmap_getbit(badsec)
 592 blkaddr_t       badsec;
 593 {
 594         uint_t  slot = badsec / 8;
 595         uint_t  field = badsec % 8;
 596         uchar_t mask;
 597
 598         mask = ALTS_BAD<<7;
 599         mask >>= field;
 600         if ((ap->ap_mapp)[slot] & mask)
 601             return (ALTS_BAD);
 602         return (ALTS_GOOD);
 603 }
 604
 605
 606 /*
 607  *      allocate a range of sectors from the alternate partition
 608  */
 609 static blkaddr_t
 610 altsmap_alloc(srt_ind, end_ind, cnt, dir)
 611 blkaddr_t       srt_ind;
 612 blkaddr_t       end_ind;
 613 int     cnt;
 614 int     dir;
 615 {
 616         blkaddr_t       i;
 617         blkaddr_t       total;
 618         blkaddr_t       first_ind;
 619
 620         for (i = srt_ind, first_ind = srt_ind, total = 0;
 621             i != end_ind; i += dir) {
 622             if ((ap->ap_memmapp)[i] == ALTS_BAD) {
 623                 total = 0;
 624                 first_ind = i + dir;
 625                 continue;
 626             }
 627             total++;
 628             if (total == cnt)
 629                 return (first_ind);
 630
 631         }
 632         return (NULL);
 633 }
 634
 635
 636
 637 /*
 638  *      bubble sort the entry table into ascending order
 639  */
 640 static void
 641 ent_sort(buf, cnt)
 642 struct  alts_ent buf[];
 643 int     cnt;
 644 {
 645 struct  alts_ent temp;
 646 int     flag;
 647 int     i, j;
 648
 649         for (i = 0; i < cnt-1; i++) {
 650             temp = buf[cnt-1];
 651             flag = 1;
 652
 653             for (j = cnt-1; j > i; j--) {
 654                 if (buf[j-1].bad_start < temp.bad_start) {
 655                     buf[j] = temp;
 656                     temp = buf[j-1];
 657                 } else {
 658                     buf[j] = buf[j-1];
 659                     flag = 0;
 660                 }
 661             }
 662             buf[i] = temp;
 663             if (flag) break;
 664         }
 665
 666 }
 667
 668
 669 /*
 670  *      compress all the contiguous bad sectors into a single entry
 671  *      in the entry table. The entry table must be sorted into ascending
 672  *      before the compression.
 673  */
 674 static void
 675 ent_compress(buf, cnt)
 676 struct  alts_ent buf[];
 677 int     cnt;
 678 {
 679 int     keyp;
 680 int     movp;
 681 int     i;
 682
 683         for (i = 0; i < cnt; i++) {
 684             if (buf[i].bad_start == (uint32_t)ALTS_ENT_EMPTY)
 685                 continue;
 686             for (keyp = i, movp = i+1; movp < cnt; movp++) {
 687                 if (buf[movp].bad_start == (uint32_t)ALTS_ENT_EMPTY)
 688                         continue;
 689                 if (buf[keyp].bad_end+1 != buf[movp].bad_start)
 690                     break;
 691                 buf[keyp].bad_end++;
 692                 buf[movp].bad_start = (uint32_t)ALTS_ENT_EMPTY;
 693             }
 694             if (movp == cnt) break;
 695         }
 696 }
 697
 698
 699 /*
 700  *      merging two entry tables into a single table. In addition,
 701  *      all empty slots in the entry table will be removed.
 702  */
 703 static int
 704 ent_merge(buf, list1, lcnt1, list2, lcnt2)
 705 struct  alts_ent buf[];
 706 struct  alts_ent list1[];
 707 int     lcnt1;
 708 struct  alts_ent list2[];
 709 int     lcnt2;
 710 {
 711         int     i;
 712         int     j1, j2;
 713
 714         for (i = 0, j1 = 0, j2 = 0; j1 < lcnt1 && j2 < lcnt2; ) {
 715             if (list1[j1].bad_start == (uint32_t)ALTS_ENT_EMPTY) {
 716                 j1++;
 717                 continue;
 718             }
 719             if (list2[j2].bad_start == (uint32_t)ALTS_ENT_EMPTY) {
 720                 j2++;
 721                 continue;
 722             }
 723             if (list1[j1].bad_start < list2[j2].bad_start)
 724                 buf[i++] = list1[j1++];
 725             else
 726                 buf[i++] = list2[j2++];
 727         }
 728         for (; j1 < lcnt1; j1++) {
 729             if (list1[j1].bad_start == (uint32_t)ALTS_ENT_EMPTY)
 730                 continue;
 731             buf[i++] = list1[j1];
 732         }
 733         for (; j2 < lcnt2; j2++) {
 734             if (list2[j2].bad_start == (uint32_t)ALTS_ENT_EMPTY)
 735                 continue;
 736             buf[i++] = list2[j2];
 737         }
 738         return (i);
 739 }
 740
 741
 742 /*
 743  *      binary search for bad sector in the alternate entry table
 744  */
 745 static int
 746 ent_bsearch(buf, cnt, key)
 747 struct  alts_ent buf[];
 748 int     cnt;
 749 struct  alts_ent *key;
 750 {
 751         int     i;
 752         int     ind;
 753         int     interval;
 754         int     mystatus = -1;
 755
 756         if (!cnt)
 757             return (mystatus);
 758
 759         for (i = 1; i <= cnt; i <<= 1)
 760             ind = i;
 761
 762         for (interval = ind; interval; ) {
 763             if ((key->bad_start >= buf[ind-1].bad_start) &&
 764                 (key->bad_start <= buf[ind-1].bad_end)) {
 765                 return (mystatus = ind-1);
 766             } else {
 767                 interval >>= 1;
 768                 if (!interval) break;
 769                 if (key->bad_start < buf[ind-1].bad_start) {
 770                     ind = ind - interval;
 771                 } else {
 772 /*      if key is larger than the last element then break       */
 773                     if (ind == cnt) break;
 774                     if ((ind+interval) <= cnt)
 775                         ind += interval;
 776                 }
 777             }
 778         }
 779         return (mystatus);
 780 }
 781
 782 /*
 783  *      check for bad sector in assigned alternate sectors
 784  */
 785 static int
 786 chk_bad_altsctr(badsec)
 787 blkaddr_t       badsec;
 788 {
 789         int     i;
 790         blkaddr_t       numsec;
 791         int     cnt = ap->ap_tblp->alts_ent_used;
 792 /*
 793  *      daddr_t intv[3];
 794  */
 795
 796         for (i = 0; i < cnt; i++) {
 797             numsec = (ap->ap_entp)[i].bad_end - (ap->ap_entp)[i].bad_start;
 798             if ((badsec >= (ap->ap_entp)[i].good_start) &&
 799                 (badsec <= ((ap->ap_entp)[i].good_start + numsec))) {
 800                 (void) fprintf(stderr,
 801                 "Bad sector %ld is an assigned alternate sector.\n", badsec);
 802                 return (66);
 803 /*
 804  *              if (!numsec) {
 805  *                  (ap->ap_entp)[i].good_start = 0;
 806  *                  return (FAILURE);
 807  *              }
 808  *              intv[0] = badsec - (ap->ap_entp)[i].good_start;
 809  *              intv[1] = 1;
 810  *              intv[2] = (ap->ap_entp)[i].good_start + numsec - badsec;
 811  */
 812             }
 813         }
 814 /*      the bad sector has already been identified as bad               */
 815         return (SUCCESS);
 816
 817 }