bootx.tproj/sl.subproj/raid.c

   1
   2 /*
   3  * Copyright (c) 2000 Apple Computer, Inc. All rights reserved.
   4  *
   5  * @APPLE_LICENSE_HEADER_START@
   6  *
   7  * The contents of this file constitute Original Code as defined in and
   8  * are subject to the Apple Public Source License Version 1.1 (the
   9  * "License").  You may not use this file except in compliance with the
  10  * License.  Please obtain a copy of the License at
  11  * http://www.apple.com/publicsource and read it before using this file.
  12  *
  13  * This Original Code and all software distributed under the License are
  14  * distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  15  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  16  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
  17  * FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT.  Please see the
  18  * License for the specific language governing rights and limitations
  19  * under the License.
  20  *
  21  * @APPLE_LICENSE_HEADER_END@
  22  */
  23 /*
  24  *  raid.c - Main functions for BootX.
  25  *
  26  *  Copyright (c) 1998-2005 Apple Computer, Inc.
  27  *
  28  *  DRI: Josh de Cesare (BootX), Soren Spies (RAID support)
  29  */
  30
  31
  32 #include <sl.h>
  33 #include <IOKit/IOKitKeys.h>
  34
  35 typedef unsigned long long  UInt64;
  36 #define KERNEL
  37 #include <IOKit/storage/RAID/AppleRAIDUserLib.h>   // hooray
  38 //#include "/System/Library/Frameworks/IOKit.framework/Versions/A/PrivateHeaders/storage/RAID/AppleRAIDUserLib.h"
  39
  40 /* things we could probably get from elsewhere */
  41 typedef enum RAIDType {
  42   kRAIDTypeUseless = -1,
  43   kRAIDTypeMirror,
  44   kRAIDTypeStripe,
  45   kRAIDTypeConcat,
  46   // kRAIDTypeFive,
  47 } RAIDType;
  48
  49
  50 /* stolen from AppleRAIDMember.h */
  51
  52 #define kAppleRAIDSignature "AppleRAIDHeader"
  53 #define kAppleRAIDHeaderSize    0x1000
  54
  55 #define ARHEADER_OFFSET(s)  ((UInt64)(s) / kAppleRAIDHeaderSize * kAppleRAIDHeaderSize - kAppleRAIDHeaderSize )
  56
  57 struct AppleRAIDHeaderV2 {
  58     char    raidSignature[16];
  59     char    raidUUID[64];
  60     char    memberUUID[64];
  61     UInt64  size;
  62     char    plist[0];
  63 };
  64 typedef struct AppleRAIDHeaderV2 AppleRAIDHeaderV2;
  65
  66
  67 /* our data structure */
  68 typedef struct RAIDMember {
  69   // our providers
  70   char      path[256];   // sized like gBootDevice
  71   UInt64    size;        // becomes data-bearing portion once known
  72   union {  // switch on totMembers
  73     struct RAIDMember **members;  // dynamic array of pointers
  74                          // totMembers big; curMembers elements
  75     CICell    ih;        // after we Open() path; NULL if useless
  76   };
  77
  78
  79   // --- everything below here used for members; not leaves ---
  80   UInt64    curOffset;  // absolute for Seek/RAIDRead()
  81   int       curMembers; // updated as we add members and do I/O
  82
  83   // derived from the header(s - struct and plist) stored in the providers
  84   char      setUUID[64]; // id used (w/seqNum) to find other members
  85   RAIDType  type;        // mirror, stripe, concat
  86   int       seqNum;      // member generation id
  87   int       totMembers;  // total members in set
  88   UInt64    chunkSize;   // stripe width
  89   UInt64    chunkCount;  // number of chunks (unused?)
  90 } RAIDDevice;  // *RAIDDevicePtr;
  91
  92 /* for our paths */
  93 #define kAppleRAIDOFPathPrefix "AppleRAID/"
  94
  95 /* -- static variables -- */
  96 static int gMaxMembers;
  97 static int gTotalMembers;
  98 static struct RAIDMember *gMembers;  // an array of structs
  99 static RAIDDevicePtr gRAIDMaster = NULL;
 100
 101 /* -- internal helper prototypes -- */
 102 static long FillInLeaf(TagPtr tagElem, RAIDDevicePtr member);
 103 static long AssimilateMember(RAIDDevicePtr member);
 104 static RAIDDevicePtr DetermineParent(TagPtr candidateDict, AppleRAIDHeaderV2*);
 105 static long AdoptChild(RAIDDevicePtr parent, RAIDDevicePtr child, TagPtr cDict);
 106 static long isComplete(RAIDDevicePtr member);
 107 static long NextPartition(char *loaderDev, char *memberDev);    // XX share?
 108 // must call these with non-"-1" offsets
 109 static long ReadMirror(RAIDDevicePtr raid, long buf, long nbytes,UInt64 offset);
 110 static long ReadStripe(RAIDDevicePtr raid, long buf, long nbytes,UInt64 offset);
 111 static long ReadConcat(RAIDDevicePtr raid, long buf, long nbytes,UInt64 offset);
 112
 113 /* -- accessors -- */
 114 static RAIDType GetRAIDType(TagPtr dict);
 115 static long long GetWholeNumber(TagPtr dict, char *key);
 116
 117 /* -- cruft XX :) -- */
 118 static void problemCode();      // need to isolate crasher
 119
 120 /* -- public helpers -- */
 121 int isRAIDPath(char *devSpec)
 122 {
 123   int rval;
 124
 125   rval = (devSpec && !strncmp(devSpec, kAppleRAIDOFPathPrefix,
 126       sizeof(kAppleRAIDOFPathPrefix)-1));
 127   return rval;
 128 }
 129
 130 /* only publicly a RAID device if it has members */
 131 /* we could have magic in our struct to be really sure :) */
 132 int isRAIDDevice(void *ih)
 133 {
 134   int rval;
 135
 136   if(!ih)  return 0;
 137
 138   RAIDDevicePtr p = (RAIDDevicePtr)ih;
 139   // is the pointer within range
 140   rval = (p >= &gMembers[0] && p < &gMembers[gTotalMembers] && p->curMembers);
 141
 142   return rval;
 143 }
 144
 145 // --- open/close/read/!/seek ---
 146
 147 // RAIDClose()
 148 void RAIDClose(RAIDDevicePtr raid)
 149 {
 150   int i = raid->totMembers;
 151   RAIDDevicePtr mem;
 152
 153   if(raid->curMembers) {
 154     while(i-- > 0) {
 155       mem = raid->members[i];
 156       if(mem) {
 157         RAIDClose(mem);
 158         raid->members[i] = NULL;
 159         if(raid->curMembers)
 160           raid->curMembers--;
 161       }
 162     }
 163   }
 164   else if(raid->ih)
 165     Close(raid->ih);
 166 }
 167
 168 // RAIDOpen()
 169 RAIDDevicePtr RAIDOpen(char *devSpec)
 170 {
 171   // steal RAID "devices"
 172   int ridx;
 173   char *p = devSpec, *endp;
 174   RAIDDevicePtr rval = NULL;
 175
 176   if(!devSpec)  return NULL;
 177
 178   // walk past kAppleRAIDOFPathPrefix
 179   while (*p && *(p++) != '/');
 180   if(*p) {
 181     ridx = strtol(p, &endp, 10);
 182     if(ridx < gTotalMembers)
 183       rval = &gMembers[ridx];
 184   }
 185
 186   return rval;
 187 }
 188
 189 // RAIDSeek()
 190 long RAIDSeek(RAIDDevicePtr raid, long long position)
 191 {
 192   if(!raid)  return -1;
 193   if(position < 0)  return -1;
 194
 195   raid->curOffset = position;
 196   return position;
 197 }
 198
 199 // RAIDRead()
 200 long RAIDRead(RAIDDevicePtr raid, long buf, long nbytes, long long offset)
 201 {
 202   long rval = -1;
 203 static long logs = 0;
 204
 205   // only RAIDRead() supports offset == -1 -> curOffset
 206   if(offset == -1)
 207     offset = raid->curOffset;
 208
 209   if(offset > raid->size) {
 210     printf("RAIDRead() error: offset (%x%x) > raid->size (%x%x)\n",
 211         offset, raid->size);
 212     return -1;
 213   }
 214
 215   if(raid->totMembers) {
 216 if(++logs < 15)
 217 printf("RAIDRead(%x (curMembers: %d), %x, %d, %x%x)\n",
 218 raid, raid->curMembers, buf, nbytes, offset);
 219     switch(raid->type) {
 220       case kRAIDTypeMirror:
 221         rval = ReadMirror(raid, buf, nbytes, offset);
 222         break;
 223
 224       case kRAIDTypeStripe:
 225         rval = ReadStripe(raid, buf, nbytes, offset);
 226         break;
 227
 228       case kRAIDTypeConcat:
 229         rval = ReadConcat(raid, buf, nbytes, offset);
 230         break;
 231
 232       // case kRAIDTypeFive:
 233       default:
 234         printf("unsupported RAID type id: %d\n", raid->type);   // XX -> isComplete?
 235         rval = -1;
 236     }
 237   }
 238   else {  // leaf member, read from the CI; we open on demand
 239     do {
 240       if(!raid->ih) {
 241         // open underlying device
 242         if(!(raid->ih = Open(raid->path)))  break;
 243       }
 244       if(Seek(raid->ih, offset) < 0)  break;
 245 //if(logs < 25)
 246 //printf("(RR): calling CI (%x from %x @ %x)\n", nbytes, raid->ih, (int)offset);
 247       rval = Read(raid->ih, buf, nbytes);
 248     } while(0);
 249   }
 250
 251 //if((raid->curMembers && logs < 15) || rval != nbytes)
 252 //printf("RAIDRead() returning %d (vs. %d)\n", rval, nbytes);
 253
 254   return rval;
 255 }
 256
 257 // read-only, man
 258 // ! long WriteToRAID(RAIDDevicePtr ... )
 259
 260
 261 // simple for now (could spare out errors, etc)
 262 static long ReadMirror(RAIDDevicePtr raid, long buf, long nbytes, UInt64 offset)
 263 {
 264   int ridx = 0;
 265
 266   // find a working member
 267   while(ridx < raid->totMembers) {
 268     if(raid->members[ridx])
 269       break;
 270     else
 271       ridx++;
 272   }
 273
 274   if(ridx == raid->totMembers)
 275     return -1;
 276
 277   return RAIDRead(raid->members[ridx], buf, nbytes, offset);
 278 }
 279
 280 static long ReadStripe(RAIDDevicePtr raid, long buf, long nbytes, UInt64 offset)
 281 {
 282   UInt64 chunkSize = raid->chunkSize;
 283   int nMems = raid->totMembers;
 284   UInt64 subChunkStart = offset % chunkSize;    // where in the final chunk?
 285
 286   UInt64 chunkIdx = offset / chunkSize;         // which chunk of all of them?
 287   int midx = chunkIdx % nMems;                  // on which member?
 288   UInt64 mChunk = chunkIdx / nMems;             // which chunk in the member?
 289   UInt64 mChunkOffset = mChunk * chunkSize;     // which offset in the member?
 290
 291   long thisTime, totalRead = 0;
 292   long bytesRead, bytesLeft = nbytes;
 293
 294   long bufp = buf;
 295
 296   if(subChunkStart + nbytes > chunkSize)
 297     thisTime = chunkSize - subChunkStart;
 298   else
 299     thisTime = nbytes;  // nbytes is within the chunk
 300
 301   // tempting to do a partial read here ...
 302
 303   while(bytesLeft /* ALT: bufp < buf + nbytes */) {
 304     bytesRead = RAIDRead(raid->members[midx], bufp, thisTime, mChunkOffset+subChunkStart);
 305     if(bytesRead == -1)  goto fail;
 306     totalRead += bytesRead;             // record what we read
 307     bytesLeft -= bytesRead;
 308     if(bytesRead != thisTime)  break;   // detect partial read and return
 309
 310     // set up for next read
 311
 312     // effect "chunkIdx++" by walking across the members
 313     midx++;                             // next member
 314     if(midx % nMems == 0) {             // did we wrap?
 315       midx = 0;                         // back to 0th member
 316       mChunkOffset += chunkSize;        // next chunk ("mChunk++")
 317     }
 318
 319     // adjust other parameters
 320     bufp += bytesRead;                  // bytesRead == thisTime
 321     if(bytesLeft > chunkSize)           // are we in the last chunk yet?
 322       thisTime = chunkSize;
 323     else
 324       thisTime = bytesLeft;
 325     subChunkStart = 0;                  // reset after first read (& beyond :P)
 326   }
 327
 328   return totalRead;
 329
 330 fail:
 331   totalRead = -1;
 332   return totalRead;
 333 }
 334
 335 // XX okay to compare UInt64 values to -1?
 336 static long ReadConcat(RAIDDevicePtr raid, long buf, long nbytes, UInt64 offset)
 337 {
 338 //static UInt64 predoffset = -1;
 339   int midx;
 340   UInt64 nextStart = 0, curStart = 0;
 341   long totalRead = 0, bytesRead;
 342
 343   // assume curMembers!=0 since RAIDRead() should be our only caller
 344   for(midx = 0; midx < raid->curMembers; midx++) {
 345     nextStart = curStart + raid->members[midx]->size;
 346
 347     // are we in range yet?
 348     if(offset < nextStart) {
 349       long thisTime;
 350       UInt64 curOffset = offset - curStart;
 351
 352       // make sure we aren't reading out too far
 353       if(offset + nbytes < nextStart)
 354         thisTime = nbytes;
 355       else
 356         thisTime = nextStart - offset;  // distance to the end
 357
 358       bytesRead = RAIDRead(raid->members[midx],buf,thisTime,curOffset);
 359       if(bytesRead == -1)  goto fail;
 360       totalRead += bytesRead;            // record what was read
 361       if(bytesRead != thisTime)  break;  // detect partial read and return
 362
 363       // XX need to lay out a volume to test crossing boundary in one read
 364       if(thisTime != nbytes) {
 365 printf("ReadConcat crossing a boundary in a single read\n");
 366         offset = nextStart;
 367         nbytes -= thisTime;
 368         buf += thisTime;
 369         continue;       // take another spin around the loop
 370       }
 371       break;    // exit from the enclosing loop
 372     }
 373     curStart = nextStart;
 374   }
 375
 376   return totalRead;
 377
 378 fail:
 379 printf("ReadConcat: %d for %x%x (ended %x%x..%x%x)\n",
 380 totalRead, offset, curStart, nextStart);
 381   totalRead = -1;
 382   return totalRead;
 383 }
 384
 385
 386 // --- seek out RAID members and build sets ---
 387
 388 /*
 389   How we find and build RAID sets (not our first stab :):
 390   if(have Boot.plist)
 391     1) initialize with the OF paths in Boot.plist (Tiger)
 392   else
 393     *) there is no else until we find a way to divine partition sizes
 394
 395   while(unread potential members)
 396     3) read new members and populate structs
 397     4) assimilate them ("resistance is futile!")
 398        * DetermineParent() looks through existing sets and creates on demand
 399        * give the child to the parent for adoption
 400        * if the parent becomes complete, proactively probe it as a member
 401 */
 402
 403 // process gBootDict looking for path/size pairs where we can sniff for RAID
 404 // allocate gMembers (3x the number of members)
 405 // make some stub members pointing to these paths
 406 long LookForRAID(TagPtr bootDict)
 407 {
 408   TagPtr partSpec;
 409 int nsuccesses = 0;
 410
 411   do {
 412     // count and allocate gMembers array
 413     // assume no Apple_RAID could contribute > 2 members
 414     if(bootDict->type == kTagTypeArray)
 415       for(partSpec = bootDict->tag; partSpec; partSpec = partSpec->tagNext)
 416         gMaxMembers += 3;       // XX [re]think degraded mirrors trying to stack
 417     else
 418       gMaxMembers = 3;
 419
 420     gMembers = AllocateBootXMemory(gMaxMembers*sizeof(RAIDDevice));
 421     if(!gMembers)  break;
 422     bzero(gMembers, gMaxMembers*sizeof(RAIDDevice));
 423
 424     // walk list of potential members, skipping on error
 425     //   FillInLeaf() on each
 426     //   AssimilateMember() on each
 427     if(bootDict->type == kTagTypeArray) {
 428       char masterMemberPath[256];
 429
 430       if(NextPartition(gBootDevice, masterMemberPath))  break;
 431
 432       for(partSpec = bootDict->tag; partSpec; partSpec = partSpec->tagNext) {
 433         RAIDDevicePtr newLeaf = &gMembers[gTotalMembers++];  // burn entries
 434         if(FillInLeaf(partSpec, newLeaf))  continue;
 435
 436         // is this the master (from whose Apple_Boot we loaded?
 437         if(FindDevice(newLeaf->path) == FindDevice(masterMemberPath)) {
 438 printf("raid: found member affiliated with our boot device\n");
 439           gRAIDMaster = newLeaf;
 440        }
 441
 442         // assertion: leaves are always complete
 443 printf("raid: assimilating leaf %x\n", newLeaf);
 444         if(AssimilateMember(newLeaf))  continue;
 445 nsuccesses++;
 446       }
 447     }
 448     // even degraded mirror (one member) is in an array
 449     else if(bootDict->type == kTagTypeDict) {
 450       if(FillInLeaf(bootDict, &gMembers[0]))  break;
 451       if(AssimilateMember(&gMembers[0]))  break;
 452       gRAIDMaster = &gMembers[1];
 453     }
 454     else
 455       break;
 456
 457 printf("LookForRAID() made %d happy structs ", nsuccesses);
 458 printf("which resulted in %d total objects\n", gTotalMembers);
 459
 460     if(isComplete(gRAIDMaster)) {
 461       int masteridx = gRAIDMaster - gMembers;
 462       sprintf(gBootDevice, "%s%d:0,\\\\tbxi",kAppleRAIDOFPathPrefix,masteridx);
 463 printf("raid: set gBootDevice to %s\n", gBootDevice);
 464     } else {
 465       if(!gRAIDMaster)
 466         printf("raid: boot-device didn't lead to a RAID device\n");
 467       else
 468         printf("raid: master RAID device %x missing members (has %d of %d)\n",
 469             gRAIDMaster, gRAIDMaster->curMembers, gRAIDMaster->totMembers);
 470       break;
 471     }
 472
 473     return 0;
 474   } while(0);
 475
 476   return -1;
 477 }
 478
 479 // FillInLeaf() fills in a member's struct so the partition can later be probed
 480 // (just need the path and size)
 481 static long FillInLeaf(TagPtr partSpec, RAIDDevicePtr newMember)
 482 {
 483   TagPtr prop;
 484   long long size;
 485   char *path;
 486   long rval = -1;
 487
 488   do {
 489     prop = GetProperty(partSpec, kIOBootDevicePathKey);
 490     if(!prop || prop->type != kTagTypeString)  break;
 491     path = prop->string + sizeof(kIODeviceTreePlane);  // +1(':') -1('\0')
 492     if((size = GetWholeNumber(partSpec, kIOBootDeviceSizeKey)) < 0)  break;
 493
 494 //printf("got path and size (%x%x)\n", size);
 495
 496     // and copy in the values
 497     if(!strcpy(newMember->path, path))  break;
 498     newMember->size = size;
 499
 500     // gMembers got the big bzero() so all else is fine
 501
 502     rval = 0;
 503   } while(0);
 504
 505   return rval;
 506 }
 507
 508 // need to extract logical bits so we can find a parent
 509 static long AssimilateMember(RAIDDevicePtr candidate)
 510 {
 511   TagPtr candDict = NULL;
 512   void *bufp = (char*)kLoadAddr;
 513   AppleRAIDHeaderV2 *cHeader = (AppleRAIDHeaderV2*)bufp;
 514   RAIDDevicePtr parent = NULL;
 515   long rval = -1;
 516
 517   do {
 518     // suck headers from candidate
 519     if(RAIDRead(candidate, (long)bufp, kAppleRAIDHeaderSize,
 520         ARHEADER_OFFSET(candidate->size)) != kAppleRAIDHeaderSize)  break;
 521 printf("raid: checking for magic: %s\n", bufp);  // should point to magic
 522
 523     // validate the magic
 524     if(strcmp(kAppleRAIDSignature, bufp)) {
 525       printf("RAID magic not found in member %x\n", candidate);
 526       break;
 527     }
 528 //printf("raid set UUID: %s\n", cHeader->raidUUID);
 529 //printf("memberUUID: %s\n", cHeader->memberUUID);
 530
 531     // batten down the size to hide the header
 532 printf("raid: member size (%x%x) -> data size (%x%x)\n",candidate->size,
 533 cHeader->size);
 534     candidate->size = cHeader->size;    // -msoft-flaot required!
 535
 536     // and skip to and parse the embedded plist (to get the type, etc)
 537     bufp += sizeof(AppleRAIDHeaderV2);
 538 //printf("bufp: %s\n", bufp);
 539     if((ParseXML(bufp, &candDict) < 0) || !candDict)  break;
 540 //printf("parsed RAID member dict (%x):\n", candDict);
 541 //DumpTag(candDict, 0);
 542 //printf("\n");
 543
 544     // DetermineParent will create a parent if it didn't already exist
 545     if(!(parent = DetermineParent(candDict, cHeader)))  break;
 546 printf("raid: %x being given to %x for adoption\n", candidate, parent);
 547     if(AdoptChild(parent, candidate, candDict))  break;
 548
 549 printf("raid: checking if set is ready to be probed...\n");
 550     if(isComplete(parent))
 551       (void)AssimilateMember(parent);  // we might be done ...
 552
 553     rval = 0;
 554   } while(0);
 555
 556   return rval;
 557 }
 558
 559 static long AdoptChild(RAIDDevicePtr parent, RAIDDevicePtr child, TagPtr cDict)
 560 {
 561   int candIdx, childSeq;
 562   long rval = -1;
 563
 564   do {
 565     if((childSeq = GetWholeNumber(cDict, kAppleRAIDSequenceNumberKey)) < 0)
 566         break;
 567
 568     // check for "one"ness early (the child might be otherwise unwanted)
 569     if(child == gRAIDMaster) {
 570 printf("raid: SUCCESSION %x was master; now to parent %x\n", child, parent);
 571       gRAIDMaster = parent;
 572     }
 573
 574     // do per-type actions (e.g. adjust size, cast out degraded mirrors, etc)
 575     switch(parent->type) {
 576       case kRAIDTypeMirror:
 577       // only want the most up to date n-way twins (n=1..k)
 578       if(childSeq < parent->seqNum) {
 579 printf("child seq # (%d) < parent's (%d) skip\n",childSeq,parent->seqNum);
 580         return 0;
 581       }
 582       if(childSeq > parent->seqNum) {
 583         int midx;
 584         // more recent; take the new seqNum and cast out old members
 585 printf("child seq (%d) > parent's (%d) update\n",childSeq,parent->seqNum);
 586         parent->seqNum = childSeq;
 587         for(midx = 0; midx < parent->totMembers; midx++)
 588           parent->members[midx] = NULL;
 589         parent->curMembers = 0;
 590       }
 591       parent->size = child->size;
 592
 593       break;
 594
 595       case kRAIDTypeStripe:
 596 printf("st parent->size(%x%x) += child->size(%x%x)\n",parent->size,child->size);
 597       parent->size += child->size;
 598       /* could validate that sizes/#totMembers match */
 599
 600       break;
 601
 602       // yes, concat and stripe are the same for now
 603       case kRAIDTypeConcat:
 604       parent->size += child->size;
 605
 606       break;
 607
 608       case kRAIDTypeUseless: return -1;  // yuck
 609     }
 610
 611     // get the index of this member in the set
 612     if((candIdx = GetWholeNumber(cDict, kAppleRAIDMemberIndexKey)) == -1) break;
 613
 614     // just in case we find the same member twice?
 615     // invariant: curMembers == PopCount(members)
 616     if(!parent->members[candIdx])
 617       parent->curMembers++;
 618     else
 619 printf("raid: members[%d] non-NULL: %x\n", candIdx, parent->members[candIdx]);
 620
 621 printf("raid: assigning %x to parent->members[%d]\n", child, candIdx);
 622     parent->members[candIdx] = child;
 623
 624     rval = 0;
 625   } while(0);
 626
 627   return rval;
 628 }
 629
 630 // aka "MakeNewParent()" if parent doesn't exist
 631 static RAIDDevicePtr DetermineParent(TagPtr cDict, AppleRAIDHeaderV2 *cHeader)
 632 {
 633   int ridx;
 634   RAIDDevicePtr rval = NULL;
 635   int seqNum = GetWholeNumber(cDict, kAppleRAIDSequenceNumberKey);
 636   int candIdx = GetWholeNumber(cDict, kAppleRAIDMemberIndexKey);
 637
 638   if(seqNum == -1 || candIdx == -1)  return rval;
 639
 640   // search all non-leaf parents for a potential match
 641   for(ridx = 0; ridx < gTotalMembers; ridx++) {
 642     RAIDDevicePtr potential = &gMembers[ridx];
 643     if(!potential->totMembers)  continue;  // not interested in children
 644     if(potential->totMembers <= candIdx)  continue;  // no slot for child
 645     if(potential->type != kRAIDTypeMirror) // mirrors will consider any child
 646       if(potential->seqNum != seqNum)  continue;  // wrong generation
 647
 648     // XX could check for UUID in members-UUID array
 649
 650     // if the IDs match, hooray
 651     if(!strcmp(cHeader->raidUUID, potential->setUUID)) {
 652 printf("raid: matched a child to a parent in %s\n", cHeader->raidUUID);
 653       rval = potential;
 654       break;
 655     }
 656   }
 657
 658
 659   // If we didn't find a parent, make one
 660   if(ridx == gTotalMembers)
 661     // get values, minimally validate, and populate new parent
 662     do {
 663       RAIDDevicePtr parent = &gMembers[gTotalMembers++];
 664       int totMembers = 0;
 665       RAIDType type;
 666       TagPtr prop;
 667       UInt64 chunkSize = 0;
 668       UInt64 chunkCount = 0;
 669
 670 printf("raid: making new parent %x\n", parent);
 671       // count up totMembers
 672       prop = GetProperty(cDict, kAppleRAIDMembersKey);
 673       if(!prop || prop->type != kTagTypeArray)  break;
 674 //printf("cDict->raidMembers:\n");
 675 //DumpTag(prop, 0);
 676 //printf("\n");
 677
 678       // count elements of the array
 679       prop = prop->tag;
 680       while(prop) {
 681         totMembers++;
 682         prop = prop->tagNext;
 683       }
 684 printf("raid: parent->totMembers: %d\n", totMembers);
 685       if(totMembers <= candIdx) {
 686 printf("raid: candidate claims index %d in a %d-member set; ignoring\n",
 687 candIdx, totMembers);
 688         break;
 689       }
 690
 691       // grab type, chunk info from child dict (sequence # above)
 692       type = GetRAIDType(cDict);
 693       if(type == kRAIDTypeUseless)  break;
 694       if(type == kRAIDTypeStripe) {
 695         chunkSize = GetWholeNumber(cDict, kAppleRAIDChunkSizeKey);
 696         if(chunkSize == -1)  break;
 697         chunkCount = GetWholeNumber(cDict, kAppleRAIDChunkCountKey);
 698         if(chunkCount == -1)  break;
 699       }
 700
 701       // and set up the parent structure's values
 702       parent->size = 0;         // let AssimilateMember increment the size
 703
 704       parent->members = AllocateBootXMemory(totMembers*sizeof(RAIDDevicePtr));
 705       if(!parent->members)  break;
 706       bzero(parent->members, totMembers*sizeof(RAIDDevicePtr));
 707
 708       // curMembers, curOffset == 0 from initial bzero()
 709
 710       if(!strcpy(parent->setUUID, cHeader->raidUUID))  break;
 711       parent->type = type;
 712       parent->seqNum = seqNum;
 713       parent->totMembers = totMembers;
 714       if(type == kRAIDTypeStripe) {
 715         parent->chunkSize = chunkSize;
 716         parent->chunkCount = chunkCount;
 717 //printf("stripe: size * count %x%x vs. size %x%x\n", chunkSize * chunkCount, cHeader->size);
 718       }
 719
 720       rval = parent;
 721     } while(0);
 722
 723   return rval;
 724 }
 725
 726 static long NextPartition(char *loaderDev, char *memberDev)
 727 {
 728   int cnt, cnt2, partNum;
 729   // stolen from main.c
 730
 731   // Find the first ':'.
 732   cnt = 0;
 733   while ((loaderDev[cnt] != '\0') && (loaderDev[cnt] != ':')) cnt++;
 734   if (loaderDev[cnt] == '\0') return -1;
 735
 736   // Find the comma after the ':'.
 737   cnt2 = cnt + 1;
 738   while ((loaderDev[cnt2]  != '\0') && (loaderDev[cnt] != ',')) cnt2++;
 739
 740   // Get just the partition number
 741   strncpy(memberDev, loaderDev + cnt + 1, cnt2 - cnt - 1);
 742   partNum = strtol(memberDev, 0, 10);
 743   if (partNum == 0) partNum = strtol(gBootFile, 0, 16);
 744
 745   // looking for the Apple_RAID following the Apple_Boot
 746   partNum++;
 747
 748   // Construct the boot-file
 749   strncpy(memberDev, loaderDev, cnt + 1);
 750   sprintf(memberDev + cnt + 1, "%d", partNum);
 751
 752   return 0;
 753 }
 754
 755 static long isComplete(RAIDDevicePtr member)
 756 {
 757   int rval = 0;
 758
 759   do {
 760     if(!member || !member->curMembers)  break;
 761
 762     switch(member->type) {
 763       case kRAIDTypeMirror:
 764         rval = (member->curMembers > 0);
 765         break;
 766
 767       case kRAIDTypeStripe:
 768       case kRAIDTypeConcat:
 769         rval = (member->curMembers == member->totMembers);
 770
 771       default:
 772         break;
 773     }
 774   } while(0);
 775
 776 printf("raid: isComplete on %x (type %d, #mems %d): %d\n",
 777 member, member->type, member->curMembers, rval);
 778   return rval;
 779 }
 780
 781
 782 // --- dictionary accessors ---
 783 static RAIDType GetRAIDType(TagPtr dict)
 784 {
 785   RAIDType type = kRAIDTypeUseless;
 786   TagPtr prop;
 787   char *typeString;
 788
 789   do {
 790     prop = GetProperty(dict, kAppleRAIDLevelNameKey);
 791     if(!prop || prop->type != kTagTypeString)  break;
 792     typeString = prop->string;
 793     switch(typeString[0]) {
 794       case 'M': type = kRAIDTypeMirror; break;
 795       case 'S': type = kRAIDTypeStripe; break;
 796       case 'C': type = kRAIDTypeConcat; break;
 797       default:
 798 printf("raid: didn't like level: %s\n", typeString);
 799         type = kRAIDTypeUseless;
 800     }
 801   } while(0);
 802
 803   return type;
 804 }
 805
 806 // "whole numbers are the counting numbers plus zero"  - math team coach
 807 // -1 indicates an error
 808 static long long GetWholeNumber(TagPtr dict, char *key)
 809 {
 810   long long num = -1;
 811   char *endp;
 812   TagPtr prop;
 813
 814   do {
 815     prop = GetProperty(dict, key);
 816     if(!prop || prop->type != kTagTypeInteger)  break;
 817     num = strtouq(prop->string, &endp, 0);   // as long as not > #mems :)
 818     if(*endp != '\0') {
 819       num = -1;
 820     }
 821   } while(0);
 822
 823   return num;
 824 }
 825
 826
 827 // -- cruft --
 828 static void problemCode()
 829 {
 830   RAIDDevice rmem, *tmem = &rmem;
 831   AppleRAIDHeaderV2 rheader, *theader = &rheader;
 832   void *fp = &problemCode;
 833
 834 printf("\n ... calling probleCode() ...\n");
 835   fp += 1;
 836 printf("populating a size member\n");
 837   theader->size = 123456789;
 838 //printf("trying to copy tmem->size = theader->size");
 839   tmem->size = theader->size;
 840 printf("dumping size: %x,%x\n", (int)(tmem->size>>32), (int)tmem);
 841 }