/ Check-in [535523e1]
Login

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview
Comment:Remove the psAligned value from the BTree structure - the pageSize is now always aligned to an 8-byte boundary. Add comments on a confusing bit of code. Ticket #1231. (CVS 2451)
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1:535523e1be692adc940d256a7b3d23c62a4cc947
User & Date: drh 2005-05-01 22:52:42
Context
2005-05-03
12:30
Make sure all data structures have 8-byte alignment - necessary for the sparc architecture and helpful on other 64-bit platforms. Ticket #1232. Also update some comments in build.c. (CVS 2452) check-in: d9418851 user: drh tags: trunk
2005-05-01
22:52
Remove the psAligned value from the BTree structure - the pageSize is now always aligned to an 8-byte boundary. Add comments on a confusing bit of code. Ticket #1231. (CVS 2451) check-in: 535523e1 user: drh tags: trunk
2005-04-29
02:10
Prevent a segfault described by ticket #1229. (CVS 2450) check-in: 0667eae9 user: drh tags: trunk
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/btree.c.

     5      5   ** a legal notice, here is a blessing:
     6      6   **
     7      7   **    May you do good and not evil.
     8      8   **    May you find forgiveness for yourself and forgive others.
     9      9   **    May you share freely, never taking more than you give.
    10     10   **
    11     11   *************************************************************************
    12         -** $Id: btree.c,v 1.256 2005/03/29 13:17:46 drh Exp $
           12  +** $Id: btree.c,v 1.257 2005/05/01 22:52:42 drh Exp $
    13     13   **
    14     14   ** This file implements a external (disk-based) database using BTrees.
    15     15   ** For a detailed discussion of BTrees, refer to
    16     16   **
    17     17   **     Donald E. Knuth, THE ART OF COMPUTER PROGRAMMING, Volume 3:
    18     18   **     "Sorting And Searching", pages 473-480. Addison-Wesley
    19     19   **     Publishing Company, Reading, Massachusetts.
................................................................................
   207    207   */
   208    208   #include "sqliteInt.h"
   209    209   #include "pager.h"
   210    210   #include "btree.h"
   211    211   #include "os.h"
   212    212   #include <assert.h>
   213    213   
   214         -/*
   215         -** This macro rounds values up so that if the value is an address it
   216         -** is guaranteed to be an address that is aligned to an 8-byte boundary.
   217         -*/
   218         -#define FORCE_ALIGNMENT(X)   (((X)+7)&~7)
   219         -
   220    214   /* The following value is the maximum cell size assuming a maximum page
   221    215   ** size give above.
   222    216   */
   223    217   #define MX_CELL_SIZE(pBt)  (pBt->pageSize-8)
   224    218   
   225    219   /* The maximum number of cells on a single page of the database.  This
   226    220   ** assumes a minimum cell size of 3 bytes.  Such small cells will be
................................................................................
   304    298     u8 minEmbedFrac;      /* Minimum payload as % of total page size */
   305    299     u8 minLeafFrac;       /* Minimum leaf payload as % of total page size */
   306    300     u8 pageSizeFixed;     /* True if the page size can no longer be changed */
   307    301   #ifndef SQLITE_OMIT_AUTOVACUUM
   308    302     u8 autoVacuum;        /* True if database supports auto-vacuum */
   309    303   #endif
   310    304     u16 pageSize;         /* Total number of bytes on a page */
   311         -  u16 psAligned;        /* pageSize rounded up to a multiple of 8 */
   312    305     u16 usableSize;       /* Number of usable bytes on each page */
   313    306     int maxLocal;         /* Maximum local payload in non-LEAFDATA tables */
   314    307     int minLocal;         /* Minimum local payload in non-LEAFDATA tables */
   315    308     int maxLeaf;          /* Maximum local payload in a LEAFDATA table */
   316    309     int minLeaf;          /* Minimum local payload in a LEAFDATA table */
   317    310     BusyHandler *pBusyHandler;   /* Callback for when there is lock contention */
   318    311   };
................................................................................
   710    703     int cellOffset;
   711    704     int nCell, cellLimit;
   712    705     u8 *used;
   713    706   
   714    707     used = sqliteMallocRaw( pPage->pBt->pageSize );
   715    708     if( used==0 ) return;
   716    709     usableSize = pPage->pBt->usableSize;
   717         -  assert( pPage->aData==&((unsigned char*)pPage)[-pPage->pBt->psAligned] );
          710  +  assert( pPage->aData==&((unsigned char*)pPage)[-pPage->pBt->pageSize] );
   718    711     hdr = pPage->hdrOffset;
   719    712     assert( hdr==(pPage->pgno==1 ? 100 : 0) );
   720    713     assert( pPage->pgno==sqlite3pager_pagenumber(pPage->aData) );
   721    714     c = pPage->aData[hdr];
   722    715     if( pPage->isInit ){
   723    716       assert( pPage->leaf == ((c & PTF_LEAF)!=0) );
   724    717       assert( pPage->zeroData == ((c & PTF_ZERODATA)!=0) );
................................................................................
  1013   1006     int nFree;         /* Number of unused bytes on the page */
  1014   1007     int top;           /* First byte of the cell content area */
  1015   1008   
  1016   1009     pBt = pPage->pBt;
  1017   1010     assert( pBt!=0 );
  1018   1011     assert( pParent==0 || pParent->pBt==pBt );
  1019   1012     assert( pPage->pgno==sqlite3pager_pagenumber(pPage->aData) );
  1020         -  assert( pPage->aData == &((unsigned char*)pPage)[-pBt->psAligned] );
         1013  +  assert( pPage->aData == &((unsigned char*)pPage)[-pBt->pageSize] );
  1021   1014     if( pPage->pParent!=pParent && (pPage->pParent!=0 || pPage->isInit) ){
  1022   1015       /* The parent page should never change unless the file is corrupt */
  1023   1016       return SQLITE_CORRUPT; /* bkpt-CORRUPT */
  1024   1017     }
  1025   1018     if( pPage->isInit ) return SQLITE_OK;
  1026   1019     if( pPage->pParent==0 && pParent!=0 ){
  1027   1020       pPage->pParent = pParent;
................................................................................
  1081   1074   static void zeroPage(MemPage *pPage, int flags){
  1082   1075     unsigned char *data = pPage->aData;
  1083   1076     Btree *pBt = pPage->pBt;
  1084   1077     int hdr = pPage->hdrOffset;
  1085   1078     int first;
  1086   1079   
  1087   1080     assert( sqlite3pager_pagenumber(data)==pPage->pgno );
  1088         -  assert( &data[pBt->psAligned] == (unsigned char*)pPage );
         1081  +  assert( &data[pBt->pageSize] == (unsigned char*)pPage );
  1089   1082     assert( sqlite3pager_iswriteable(data) );
  1090   1083     memset(&data[hdr], 0, pBt->usableSize - hdr);
  1091   1084     data[hdr] = flags;
  1092   1085     first = hdr + 8 + 4*((flags&PTF_LEAF)==0);
  1093   1086     memset(&data[hdr+1], 0, 4);
  1094   1087     data[hdr+7] = 0;
  1095   1088     put2byte(&data[hdr+5], pBt->usableSize);
................................................................................
  1110   1103   */
  1111   1104   static int getPage(Btree *pBt, Pgno pgno, MemPage **ppPage){
  1112   1105     int rc;
  1113   1106     unsigned char *aData;
  1114   1107     MemPage *pPage;
  1115   1108     rc = sqlite3pager_get(pBt->pPager, pgno, (void**)&aData);
  1116   1109     if( rc ) return rc;
  1117         -  pPage = (MemPage*)&aData[pBt->psAligned];
         1110  +  pPage = (MemPage*)&aData[pBt->pageSize];
  1118   1111     pPage->aData = aData;
  1119   1112     pPage->pBt = pBt;
  1120   1113     pPage->pgno = pgno;
  1121   1114     pPage->hdrOffset = pPage->pgno==1 ? 100 : 0;
  1122   1115     *ppPage = pPage;
  1123   1116     return SQLITE_OK;
  1124   1117   }
................................................................................
  1149   1142   ** Release a MemPage.  This should be called once for each prior
  1150   1143   ** call to getPage.
  1151   1144   */
  1152   1145   static void releasePage(MemPage *pPage){
  1153   1146     if( pPage ){
  1154   1147       assert( pPage->aData );
  1155   1148       assert( pPage->pBt );
  1156         -    assert( &pPage->aData[pPage->pBt->psAligned]==(unsigned char*)pPage );
         1149  +    assert( &pPage->aData[pPage->pBt->pageSize]==(unsigned char*)pPage );
  1157   1150       sqlite3pager_unref(pPage->aData);
  1158   1151     }
  1159   1152   }
  1160   1153   
  1161   1154   /*
  1162   1155   ** This routine is called when the reference count for a page
  1163   1156   ** reaches zero.  We need to unref the pParent pointer when that
  1164   1157   ** happens.
  1165   1158   */
  1166   1159   static void pageDestructor(void *pData, int pageSize){
  1167         -  MemPage *pPage = (MemPage*)&((char*)pData)[FORCE_ALIGNMENT(pageSize)];
         1160  +  MemPage *pPage;
         1161  +  assert( (pageSize & 7)==0 );
         1162  +  pPage = (MemPage*)&((char*)pData)[pageSize];
  1168   1163     if( pPage->pParent ){
  1169   1164       MemPage *pParent = pPage->pParent;
  1170   1165       pPage->pParent = 0;
  1171   1166       releasePage(pParent);
  1172   1167     }
  1173   1168     pPage->isInit = 0;
  1174   1169   }
................................................................................
  1178   1173   ** so that the cache is restored to its original state at the start of
  1179   1174   ** the transaction, for each page restored this routine is called.
  1180   1175   **
  1181   1176   ** This routine needs to reset the extra data section at the end of the
  1182   1177   ** page to agree with the restored data.
  1183   1178   */
  1184   1179   static void pageReinit(void *pData, int pageSize){
  1185         -  MemPage *pPage = (MemPage*)&((char*)pData)[FORCE_ALIGNMENT(pageSize)];
         1180  +  MemPage *pPage;
         1181  +  assert( (pageSize & 7)==0 );
         1182  +  pPage = (MemPage*)&((char*)pData)[pageSize];
  1186   1183     if( pPage->isInit ){
  1187   1184       pPage->isInit = 0;
  1188   1185       initPage(pPage, pPage->pParent);
  1189   1186     }
  1190   1187   }
  1191   1188   
  1192   1189   /*
................................................................................
  1234   1231     sqlite3pager_set_destructor(pBt->pPager, pageDestructor);
  1235   1232     sqlite3pager_set_reiniter(pBt->pPager, pageReinit);
  1236   1233     pBt->pCursor = 0;
  1237   1234     pBt->pPage1 = 0;
  1238   1235     pBt->readOnly = sqlite3pager_isreadonly(pBt->pPager);
  1239   1236     sqlite3pager_read_fileheader(pBt->pPager, sizeof(zDbHeader), zDbHeader);
  1240   1237     pBt->pageSize = get2byte(&zDbHeader[16]);
  1241         -  if( pBt->pageSize<512 || pBt->pageSize>SQLITE_MAX_PAGE_SIZE ){
         1238  +  if( pBt->pageSize<512 || pBt->pageSize>SQLITE_MAX_PAGE_SIZE
         1239  +       || ((pBt->pageSize-1)&pBt->pageSize)!=0 ){
  1242   1240       pBt->pageSize = SQLITE_DEFAULT_PAGE_SIZE;
  1243   1241       pBt->maxEmbedFrac = 64;   /* 25% */
  1244   1242       pBt->minEmbedFrac = 32;   /* 12.5% */
  1245   1243       pBt->minLeafFrac = 32;    /* 12.5% */
  1246   1244   #ifndef SQLITE_OMIT_AUTOVACUUM
  1247   1245       /* If the magic name ":memory:" will create an in-memory database, then
  1248   1246       ** do not set the auto-vacuum flag, even if SQLITE_DEFAULT_AUTOVACUUM
................................................................................
  1266   1264       pBt->minLeafFrac = zDbHeader[23];
  1267   1265       pBt->pageSizeFixed = 1;
  1268   1266   #ifndef SQLITE_OMIT_AUTOVACUUM
  1269   1267       pBt->autoVacuum = (get4byte(&zDbHeader[36 + 4*4])?1:0);
  1270   1268   #endif
  1271   1269     }
  1272   1270     pBt->usableSize = pBt->pageSize - nReserve;
  1273         -  pBt->psAligned = FORCE_ALIGNMENT(pBt->pageSize);
         1271  +  assert( (pBt->pageSize & 7)==0 );  /* 8-byte alignment of pageSize */
  1274   1272     sqlite3pager_set_pagesize(pBt->pPager, pBt->pageSize);
  1275   1273     *ppBtree = pBt;
  1276   1274     return SQLITE_OK;
  1277   1275   }
  1278   1276   
  1279   1277   /*
  1280   1278   ** Close an open database and invalidate all cursors.
................................................................................
  1353   1351       return SQLITE_READONLY;
  1354   1352     }
  1355   1353     if( nReserve<0 ){
  1356   1354       nReserve = pBt->pageSize - pBt->usableSize;
  1357   1355     }
  1358   1356     if( pageSize>=512 && pageSize<=SQLITE_MAX_PAGE_SIZE &&
  1359   1357           ((pageSize-1)&pageSize)==0 ){
         1358  +    assert( (pageSize & 7)==0 );
  1360   1359       pBt->pageSize = pageSize;
  1361         -    pBt->psAligned = FORCE_ALIGNMENT(pageSize);
  1362   1360       sqlite3pager_set_pagesize(pBt->pPager, pageSize);
  1363   1361     }
  1364   1362     pBt->usableSize = pBt->pageSize - nReserve;
  1365   1363     return SQLITE_OK;
  1366   1364   }
  1367   1365   
  1368   1366   /*
................................................................................
  1414   1412   ** SQLITE_OK is returned on success.  If the file is not a
  1415   1413   ** well-formed database file, then SQLITE_CORRUPT is returned.
  1416   1414   ** SQLITE_BUSY is returned if the database is locked.  SQLITE_NOMEM
  1417   1415   ** is returned if we run out of memory.  SQLITE_PROTOCOL is returned
  1418   1416   ** if there is a locking protocol violation.
  1419   1417   */
  1420   1418   static int lockBtree(Btree *pBt){
  1421         -  int rc;
         1419  +  int rc, pageSize;
  1422   1420     MemPage *pPage1;
  1423   1421     if( pBt->pPage1 ) return SQLITE_OK;
  1424   1422     rc = getPage(pBt, 1, &pPage1);
  1425   1423     if( rc!=SQLITE_OK ) return rc;
  1426   1424     
  1427   1425   
  1428   1426     /* Do some checking to help insure the file we opened really is
................................................................................
  1433   1431       u8 *page1 = pPage1->aData;
  1434   1432       if( memcmp(page1, zMagicHeader, 16)!=0 ){
  1435   1433         goto page1_init_failed;
  1436   1434       }
  1437   1435       if( page1[18]>1 || page1[19]>1 ){
  1438   1436         goto page1_init_failed;
  1439   1437       }
  1440         -    pBt->pageSize = get2byte(&page1[16]);
  1441         -    pBt->usableSize = pBt->pageSize - page1[20];
         1438  +    pageSize = get2byte(&page1[16]);
         1439  +    if( ((pageSize-1)&pageSize)!=0 ){
         1440  +      goto page1_init_failed;
         1441  +    }
         1442  +    assert( (pageSize & 7)==0 );
         1443  +    pBt->pageSize = pageSize;
         1444  +    pBt->usableSize = pageSize - page1[20];
  1442   1445       if( pBt->usableSize<500 ){
  1443   1446         goto page1_init_failed;
  1444   1447       }
  1445         -    pBt->psAligned = FORCE_ALIGNMENT(pBt->pageSize);
  1446   1448       pBt->maxEmbedFrac = page1[21];
  1447   1449       pBt->minEmbedFrac = page1[22];
  1448   1450       pBt->minLeafFrac = page1[23];
  1449   1451   #ifndef SQLITE_OMIT_AUTOVACUUM
  1450   1452       pBt->autoVacuum = (get4byte(&page1[36 + 4*4])?1:0);
  1451   1453   #endif
  1452   1454     }
................................................................................
  1505   1507   **
  1506   1508   ** If there is a transaction in progress, this routine is a no-op.
  1507   1509   */
  1508   1510   static void unlockBtreeIfUnused(Btree *pBt){
  1509   1511     if( pBt->inTrans==TRANS_NONE && pBt->pCursor==0 && pBt->pPage1!=0 ){
  1510   1512       if( pBt->pPage1->aData==0 ){
  1511   1513         MemPage *pPage = pBt->pPage1;
  1512         -      pPage->aData = &((char*)pPage)[-pBt->psAligned];
         1514  +      pPage->aData = &((char*)pPage)[-pBt->pageSize];
  1513   1515         pPage->pBt = pBt;
  1514   1516         pPage->pgno = 1;
  1515   1517       }
  1516   1518       releasePage(pBt->pPage1);
  1517   1519       pBt->pPage1 = 0;
  1518   1520       pBt->inStmt = 0;
  1519   1521     }
................................................................................
  3377   3379     MemPage *pThis;
  3378   3380     unsigned char *aData;
  3379   3381   
  3380   3382     if( pgno==0 ) return SQLITE_OK;
  3381   3383     assert( pBt->pPager!=0 );
  3382   3384     aData = sqlite3pager_lookup(pBt->pPager, pgno);
  3383   3385     if( aData ){
  3384         -    pThis = (MemPage*)&aData[pBt->psAligned];
         3386  +    pThis = (MemPage*)&aData[pBt->pageSize];
  3385   3387       assert( pThis->aData==aData );
  3386   3388       if( pThis->isInit ){
  3387   3389         if( pThis->pParent!=pNewParent ){
  3388   3390           if( pThis->pParent ) sqlite3pager_unref(pThis->pParent->aData);
  3389   3391           pThis->pParent = pNewParent;
  3390   3392           if( pNewParent ) sqlite3pager_ref(pNewParent->aData);
  3391   3393         }
................................................................................
  3891   3893     /*
  3892   3894     ** Allocate space for memory structures
  3893   3895     */
  3894   3896     apCell = sqliteMallocRaw( 
  3895   3897          nMaxCells*sizeof(u8*)                           /* apCell */
  3896   3898        + nMaxCells*sizeof(int)                           /* szCell */
  3897   3899        + sizeof(MemPage)*NB                              /* aCopy */
  3898         -     + pBt->psAligned*(5+NB)                           /* aSpace */
         3900  +     + pBt->pageSize*(5+NB)                            /* aSpace */
  3899   3901        + (ISAUTOVACUUM ? nMaxCells : 0)     /* aFrom */
  3900   3902     );
  3901   3903     if( apCell==0 ){
  3902   3904       rc = SQLITE_NOMEM;
  3903   3905       goto balance_cleanup;
  3904   3906     }
  3905   3907     szCell = (int*)&apCell[nMaxCells];
  3906   3908     aCopy[0] = (u8*)&szCell[nMaxCells];
  3907   3909     for(i=1; i<NB; i++){
  3908         -    aCopy[i] = &aCopy[i-1][pBt->psAligned+sizeof(MemPage)];
         3910  +    aCopy[i] = &aCopy[i-1][pBt->pageSize+sizeof(MemPage)];
  3909   3911     }
  3910         -  aSpace = &aCopy[NB-1][pBt->psAligned+sizeof(MemPage)];
         3912  +  aSpace = &aCopy[NB-1][pBt->pageSize+sizeof(MemPage)];
  3911   3913   #ifndef SQLITE_OMIT_AUTOVACUUM
  3912   3914     if( pBt->autoVacuum ){
  3913         -    aFrom = &aSpace[5*pBt->psAligned];
         3915  +    aFrom = &aSpace[5*pBt->pageSize];
  3914   3916     }
  3915   3917   #endif
  3916   3918     
  3917   3919     /*
  3918   3920     ** Make copies of the content of pPage and its siblings into aOld[].
  3919   3921     ** The rest of this function will use data from the copies rather
  3920   3922     ** that the original pages since the original pages will be in the
  3921   3923     ** process of being overwritten.
  3922   3924     */
  3923   3925     for(i=0; i<nOld; i++){
  3924         -    MemPage *p = apCopy[i] = (MemPage*)&aCopy[i][pBt->psAligned];
  3925         -    p->aData = &((u8*)p)[-pBt->psAligned];
  3926         -    memcpy(p->aData, apOld[i]->aData, pBt->psAligned + sizeof(MemPage));
  3927         -    p->aData = &((u8*)p)[-pBt->psAligned];
         3926  +    MemPage *p = apCopy[i] = (MemPage*)&aCopy[i][pBt->pageSize];
         3927  +    assert( (((long long unsigned int)p) & 7)==0 );
         3928  +    p->aData = &((u8*)p)[-pBt->pageSize];
         3929  +    memcpy(p->aData, apOld[i]->aData, pBt->pageSize + sizeof(MemPage));
         3930  +    /* The memcpy() above changes the value of p->aData so we have to
         3931  +    ** set it again. */
         3932  +    assert( (((long long unsigned int)p) & 7)==0 );
         3933  +    p->aData = &((u8*)p)[-pBt->pageSize];
  3928   3934     }
  3929   3935   
  3930   3936     /*
  3931   3937     ** Load pointers to all cells on sibling pages and the divider cells
  3932   3938     ** into the local apCell[] array.  Make copies of the divider cells
  3933   3939     ** into space obtained form aSpace[] and remove the the divider Cells
  3934   3940     ** from pParent.
................................................................................
  3978   3984           dropCell(pParent, nxDiv, sz);
  3979   3985         }else{
  3980   3986           u8 *pTemp;
  3981   3987           assert( nCell<nMaxCells );
  3982   3988           szCell[nCell] = sz;
  3983   3989           pTemp = &aSpace[iSpace];
  3984   3990           iSpace += sz;
  3985         -        assert( iSpace<=pBt->psAligned*5 );
         3991  +        assert( iSpace<=pBt->pageSize*5 );
  3986   3992           memcpy(pTemp, apDiv[i], sz);
  3987   3993           apCell[nCell] = pTemp+leafCorrection;
  3988   3994   #ifndef SQLITE_OMIT_AUTOVACUUM
  3989   3995           if( pBt->autoVacuum ){
  3990   3996             aFrom[nCell] = 0xFF;
  3991   3997           }
  3992   3998   #endif
................................................................................
  4203   4209           */
  4204   4210           CellInfo info;
  4205   4211           j--;
  4206   4212           parseCellPtr(pNew, apCell[j], &info);
  4207   4213           pCell = &aSpace[iSpace];
  4208   4214           fillInCell(pParent, pCell, 0, info.nKey, 0, 0, &sz);
  4209   4215           iSpace += sz;
  4210         -        assert( iSpace<=pBt->psAligned*5 );
         4216  +        assert( iSpace<=pBt->pageSize*5 );
  4211   4217           pTemp = 0;
  4212   4218         }else{
  4213   4219           pCell -= 4;
  4214   4220           pTemp = &aSpace[iSpace];
  4215   4221           iSpace += sz;
  4216         -        assert( iSpace<=pBt->psAligned*5 );
         4222  +        assert( iSpace<=pBt->pageSize*5 );
  4217   4223         }
  4218   4224         rc = insertCell(pParent, nxDiv, pCell, sz, pTemp, 4);
  4219   4225         if( rc!=SQLITE_OK ) goto balance_cleanup;
  4220   4226         put4byte(findOverflowCell(pParent,nxDiv), pNew->pgno);
  4221   4227   #ifndef SQLITE_OMIT_AUTOVACUUM
  4222   4228         /* If this is an auto-vacuum database, and not a leaf-data tree,
  4223   4229         ** then update the pointer map with an entry for the overflow page