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 either device doesn't exist (e.g. if both FindDevice calls
 438         // returned NULL), we'd fail later.
 439         if(FindDevice(newLeaf->path) == FindDevice(masterMemberPath)) {
 440           printf("raid: found member affiliated with our boot device\n");
 441           gRAIDMaster = newLeaf;
 442        }
 443
 444         // assertion: leaves are always complete
 445 printf("raid: assimilating leaf %x\n", newLeaf);
 446         if(AssimilateMember(newLeaf))  continue;
 447 nsuccesses++;
 448       }
 449     }
 450     // even degraded mirror (one member) is in an array
 451     else if(bootDict->type == kTagTypeDict) {
 452       if(FillInLeaf(bootDict, &gMembers[0]))  break;
 453       if(AssimilateMember(&gMembers[0]))  break;
 454       gRAIDMaster = &gMembers[1];
 455     }
 456     else
 457       break;
 458
 459 printf("LookForRAID() made %d happy structs ", nsuccesses);
 460 printf("which resulted in %d total objects\n", gTotalMembers);
 461
 462     if(isComplete(gRAIDMaster)) {
 463       int masteridx = gRAIDMaster - gMembers;
 464       sprintf(gBootDevice, "%s%d:0,\\\\tbxi",kAppleRAIDOFPathPrefix,masteridx);
 465 printf("raid: set gBootDevice to %s\n", gBootDevice);
 466     } else {
 467       if(!gRAIDMaster)
 468         printf("raid: boot-device didn't lead to a RAID device\n");
 469       else
 470         printf("raid: master RAID device %x missing members (has %d of %d)\n",
 471             gRAIDMaster, gRAIDMaster->curMembers, gRAIDMaster->totMembers);
 472       break;
 473     }
 474
 475     return 0;
 476   } while(0);
 477
 478   return -1;
 479 }
 480
 481 // FillInLeaf() fills in a member's struct so the partition can later be probed
 482 // (just need the path and size)
 483 static long FillInLeaf(TagPtr partSpec, RAIDDevicePtr newMember)
 484 {
 485   TagPtr prop;
 486   long long size;
 487   char *path;
 488   long rval = -1;
 489
 490   do {
 491     prop = GetProperty(partSpec, kIOBootDevicePathKey);
 492     if(!prop || prop->type != kTagTypeString)  break;
 493     path = prop->string + sizeof(kIODeviceTreePlane);  // +1(':') -1('\0')
 494     if((size = GetWholeNumber(partSpec, kIOBootDeviceSizeKey)) < 0)  break;
 495
 496 //printf("got path and size (%x%x)\n", size);
 497
 498     // and copy in the values
 499     if(!strcpy(newMember->path, path))  break;
 500     newMember->size = size;
 501
 502     // gMembers got the big bzero() so all else is fine
 503
 504     rval = 0;
 505   } while(0);
 506
 507   return rval;
 508 }
 509
 510 // need to extract logical bits so we can find a parent
 511 static long AssimilateMember(RAIDDevicePtr candidate)
 512 {
 513   TagPtr candDict = NULL;
 514   void *bufp = (char*)kLoadAddr;
 515   AppleRAIDHeaderV2 *cHeader = (AppleRAIDHeaderV2*)bufp;
 516   RAIDDevicePtr parent = NULL;
 517   long rval = -1;
 518
 519   do {
 520     // suck headers from candidate
 521     if(RAIDRead(candidate, (long)bufp, kAppleRAIDHeaderSize,
 522         ARHEADER_OFFSET(candidate->size)) != kAppleRAIDHeaderSize)  break;
 523 printf("raid: checking for magic: %s\n", bufp);  // should point to magic
 524
 525     // validate the magic
 526     if(strcmp(kAppleRAIDSignature, bufp)) {
 527       printf("RAID magic not found in member %x\n", candidate);
 528       break;
 529     }
 530 //printf("raid set UUID: %s\n", cHeader->raidUUID);
 531 //printf("memberUUID: %s\n", cHeader->memberUUID);
 532
 533     // batten down the size to hide the header
 534 printf("raid: member size (%x%x) -> data size (%x%x)\n",candidate->size,
 535 cHeader->size);
 536     candidate->size = cHeader->size;    // -msoft-flaot required!
 537
 538     // and skip to and parse the embedded plist (to get the type, etc)
 539     bufp += sizeof(AppleRAIDHeaderV2);
 540 //printf("bufp: %s\n", bufp);
 541     if((ParseXML(bufp, &candDict) < 0) || !candDict)  break;
 542 //printf("parsed RAID member dict (%x):\n", candDict);
 543 //DumpTag(candDict, 0);
 544 //printf("\n");
 545
 546     // DetermineParent will create a parent if it didn't already exist
 547     if(!(parent = DetermineParent(candDict, cHeader)))  break;
 548 printf("raid: %x being given to %x for adoption\n", candidate, parent);
 549     if(AdoptChild(parent, candidate, candDict))  break;
 550
 551 printf("raid: checking if set is ready to be probed...\n");
 552     if(isComplete(parent))
 553       (void)AssimilateMember(parent);  // we might be done ...
 554
 555     rval = 0;
 556   } while(0);
 557
 558   return rval;
 559 }
 560
 561 static long AdoptChild(RAIDDevicePtr parent, RAIDDevicePtr child, TagPtr cDict)
 562 {
 563   int candIdx, childSeq;
 564   long rval = -1;
 565
 566   do {
 567     if((childSeq = GetWholeNumber(cDict, kAppleRAIDSequenceNumberKey)) < 0)
 568         break;
 569
 570     // check for "one"ness early (the child might be otherwise unwanted)
 571     if(child == gRAIDMaster) {
 572 printf("raid: SUCCESSION %x was master; now to parent %x\n", child, parent);
 573       gRAIDMaster = parent;
 574     }
 575
 576     // do per-type actions (e.g. adjust size, cast out degraded mirrors, etc)
 577     switch(parent->type) {
 578       case kRAIDTypeMirror:
 579       // only want the most up to date n-way twins (n=1..k)
 580       if(childSeq < parent->seqNum) {
 581 printf("child seq # (%d) < parent's (%d) skip\n",childSeq,parent->seqNum);
 582         return 0;
 583       }
 584       if(childSeq > parent->seqNum) {
 585         int midx;
 586         // more recent; take the new seqNum and cast out old members
 587 printf("child seq (%d) > parent's (%d) update\n",childSeq,parent->seqNum);
 588         parent->seqNum = childSeq;
 589         for(midx = 0; midx < parent->totMembers; midx++)
 590           parent->members[midx] = NULL;
 591         parent->curMembers = 0;
 592       }
 593       parent->size = child->size;
 594
 595       break;
 596
 597       case kRAIDTypeStripe:
 598 printf("st parent->size(%x%x) += child->size(%x%x)\n",parent->size,child->size);
 599       parent->size += child->size;
 600       /* could validate that sizes/#totMembers match */
 601
 602       break;
 603
 604       // yes, concat and stripe are the same for now
 605       case kRAIDTypeConcat:
 606       parent->size += child->size;
 607
 608       break;
 609
 610       case kRAIDTypeUseless: return -1;  // yuck
 611     }
 612
 613     // get the index of this member in the set
 614     if((candIdx = GetWholeNumber(cDict, kAppleRAIDMemberIndexKey)) == -1) break;
 615
 616     // just in case we find the same member twice?
 617     // invariant: curMembers == PopCount(members)
 618     if(!parent->members[candIdx])
 619       parent->curMembers++;
 620     else
 621 printf("raid: members[%d] non-NULL: %x\n", candIdx, parent->members[candIdx]);
 622
 623 printf("raid: assigning %x to parent->members[%d]\n", child, candIdx);
 624     parent->members[candIdx] = child;
 625
 626     rval = 0;
 627   } while(0);
 628
 629   return rval;
 630 }
 631
 632 // aka "MakeNewParent()" if parent doesn't exist
 633 static RAIDDevicePtr DetermineParent(TagPtr cDict, AppleRAIDHeaderV2 *cHeader)
 634 {
 635   int ridx;
 636   RAIDDevicePtr rval = NULL;
 637   int seqNum = GetWholeNumber(cDict, kAppleRAIDSequenceNumberKey);
 638   int candIdx = GetWholeNumber(cDict, kAppleRAIDMemberIndexKey);
 639
 640   if(seqNum == -1 || candIdx == -1)  return rval;
 641
 642   // search all non-leaf parents for a potential match
 643   for(ridx = 0; ridx < gTotalMembers; ridx++) {
 644     RAIDDevicePtr potential = &gMembers[ridx];
 645     if(!potential->totMembers)  continue;  // not interested in children
 646     if(potential->totMembers <= candIdx)  continue;  // no slot for child
 647     if(potential->type != kRAIDTypeMirror) // mirrors will consider any child
 648       if(potential->seqNum != seqNum)  continue;  // wrong generation
 649
 650     // XX could check for UUID in members-UUID array
 651
 652     // if the IDs match, hooray
 653     if(!strcmp(cHeader->raidUUID, potential->setUUID)) {
 654 printf("raid: matched a child to a parent in %s\n", cHeader->raidUUID);
 655       rval = potential;
 656       break;
 657     }
 658   }
 659
 660
 661   // If we didn't find a parent, make one
 662   if(ridx == gTotalMembers)
 663     // get values, minimally validate, and populate new parent
 664     do {
 665       RAIDDevicePtr parent = &gMembers[gTotalMembers++];
 666       int totMembers = 0;
 667       RAIDType type;
 668       TagPtr prop;
 669       UInt64 chunkSize = 0;
 670       UInt64 chunkCount = 0;
 671
 672 printf("raid: making new parent %x\n", parent);
 673       // count up totMembers
 674       prop = GetProperty(cDict, kAppleRAIDMembersKey);
 675       if(!prop || prop->type != kTagTypeArray)  break;
 676 //printf("cDict->raidMembers:\n");
 677 //DumpTag(prop, 0);
 678 //printf("\n");
 679
 680       // count elements of the array
 681       prop = prop->tag;
 682       while(prop) {
 683         totMembers++;
 684         prop = prop->tagNext;
 685       }
 686 printf("raid: parent->totMembers: %d\n", totMembers);
 687       if(totMembers <= candIdx) {
 688 printf("raid: candidate claims index %d in a %d-member set; ignoring\n",
 689 candIdx, totMembers);
 690         break;
 691       }
 692
 693       // grab type, chunk info from child dict (sequence # above)
 694       type = GetRAIDType(cDict);
 695       if(type == kRAIDTypeUseless)  break;
 696       if(type == kRAIDTypeStripe) {
 697         chunkSize = GetWholeNumber(cDict, kAppleRAIDChunkSizeKey);
 698         if(chunkSize == -1)  break;
 699         chunkCount = GetWholeNumber(cDict, kAppleRAIDChunkCountKey);
 700         if(chunkCount == -1)  break;
 701       }
 702
 703       // and set up the parent structure's values
 704       parent->size = 0;         // let AssimilateMember increment the size
 705
 706       parent->members = AllocateBootXMemory(totMembers*sizeof(RAIDDevicePtr));
 707       if(!parent->members)  break;
 708       bzero(parent->members, totMembers*sizeof(RAIDDevicePtr));
 709
 710       // curMembers, curOffset == 0 from initial bzero()
 711
 712       if(!strcpy(parent->setUUID, cHeader->raidUUID))  break;
 713       parent->type = type;
 714       parent->seqNum = seqNum;
 715       parent->totMembers = totMembers;
 716       if(type == kRAIDTypeStripe) {
 717         parent->chunkSize = chunkSize;
 718         parent->chunkCount = chunkCount;
 719 //printf("stripe: size * count %x%x vs. size %x%x\n", chunkSize * chunkCount, cHeader->size);
 720       }
 721
 722       rval = parent;
 723     } while(0);
 724
 725   return rval;
 726 }
 727
 728 static long NextPartition(char *loaderDev, char *memberDev)
 729 {
 730   int cnt, cnt2, partNum;
 731   // stolen from main.c
 732
 733   // Find the first ':'.
 734   cnt = 0;
 735   while ((loaderDev[cnt] != '\0') && (loaderDev[cnt] != ':')) cnt++;
 736   if (loaderDev[cnt] == '\0') return -1;
 737
 738   // Find the comma after the ':'.
 739   cnt2 = cnt + 1;
 740   while ((loaderDev[cnt2]  != '\0') && (loaderDev[cnt] != ',')) cnt2++;
 741
 742   // Get just the partition number
 743   strncpy(memberDev, loaderDev + cnt + 1, cnt2 - cnt - 1);
 744   partNum = strtol(memberDev, 0, 10);
 745   if (partNum == 0) partNum = strtol(gBootFile, 0, 16);
 746
 747   // looking for the Apple_RAID following the Apple_Boot
 748   partNum++;
 749
 750   // Construct the boot-file
 751   strncpy(memberDev, loaderDev, cnt + 1);
 752   sprintf(memberDev + cnt + 1, "%d", partNum);
 753
 754   return 0;
 755 }
 756
 757 static long isComplete(RAIDDevicePtr member)
 758 {
 759   int rval = 0;
 760
 761   do {
 762     if(!member || !member->curMembers)  break;
 763
 764     switch(member->type) {
 765       case kRAIDTypeMirror:
 766         rval = (member->curMembers > 0);
 767         break;
 768
 769       case kRAIDTypeStripe:
 770       case kRAIDTypeConcat:
 771         rval = (member->curMembers == member->totMembers);
 772
 773       default:
 774         break;
 775     }
 776   } while(0);
 777
 778 printf("raid: isComplete on %x (type %d, #mems %d): %d\n",
 779 member, member->type, member->curMembers, rval);
 780   return rval;
 781 }
 782
 783
 784 // --- dictionary accessors ---
 785 static RAIDType GetRAIDType(TagPtr dict)
 786 {
 787   RAIDType type = kRAIDTypeUseless;
 788   TagPtr prop;
 789   char *typeString;
 790
 791   do {
 792     prop = GetProperty(dict, kAppleRAIDLevelNameKey);
 793     if(!prop || prop->type != kTagTypeString)  break;
 794     typeString = prop->string;
 795     switch(typeString[0]) {
 796       case 'M': type = kRAIDTypeMirror; break;
 797       case 'S': type = kRAIDTypeStripe; break;
 798       case 'C': type = kRAIDTypeConcat; break;
 799       default:
 800 printf("raid: didn't like level: %s\n", typeString);
 801         type = kRAIDTypeUseless;
 802     }
 803   } while(0);
 804
 805   return type;
 806 }
 807
 808 // "whole numbers are the counting numbers plus zero"  - math team coach
 809 // -1 indicates an error
 810 static long long GetWholeNumber(TagPtr dict, char *key)
 811 {
 812   long long num = -1;
 813   char *endp;
 814   TagPtr prop;
 815
 816   do {
 817     prop = GetProperty(dict, key);
 818     if(!prop || prop->type != kTagTypeInteger)  break;
 819     num = strtouq(prop->string, &endp, 0);   // as long as not > #mems :)
 820     if(*endp != '\0') {
 821       num = -1;
 822     }
 823   } while(0);
 824
 825   return num;
 826 }
 827
 828
 829 // -- cruft --
 830 static void problemCode()
 831 {
 832   RAIDDevice rmem, *tmem = &rmem;
 833   AppleRAIDHeaderV2 rheader, *theader = &rheader;
 834   void *fp = &problemCode;
 835
 836 printf("\n ... calling probleCode() ...\n");
 837   fp += 1;
 838 printf("populating a size member\n");
 839   theader->size = 123456789;
 840 //printf("trying to copy tmem->size = theader->size");
 841   tmem->size = theader->size;
 842 printf("dumping size: %x,%x\n", (int)(tmem->size>>32), (int)tmem);
 843 }