db_upg_opd.c

00001 /*-
00002  * See the file LICENSE for redistribution information.
00003  *
00004  * Copyright (c) 1996, 1997, 1998, 1999, 2000
00005  * Sleepycat Software. All rights reserved.
00006  */
00007 
00008 #include "config.h"
00009 
00010 #ifndef lint
00011 static const char revid[] = "$Id: db__upg__opd_8c-source.html,v 1.1 2008年06月08日 10:18:21 sebdiaz Exp $";
00012 #endif /* not lint */
00013 
00014 #ifndef NO_SYSTEM_INCLUDES
00015 #include <sys/types.h>
00016 
00017 #include <errno.h>
00018 #include <string.h>
00019 #endif
00020 
00021 #include "db_int.h"
00022 #include "db_page.h"
00023 #include "db_swap.h"
00024 #include "btree.h"
00025 #include "hash.h"
00026 #include "qam.h"
00027 
00028 static int __db_build_bi __P((DB *, DB_FH *, PAGE *, PAGE *, u_int32_t, int *));
00029 static int __db_build_ri __P((DB *, DB_FH *, PAGE *, PAGE *, u_int32_t, int *));
00030 static int __db_up_ovref __P((DB *, DB_FH *, db_pgno_t));
00031 
00032 #define GET_PAGE(dbp, fhp, pgno, page) { \
00033  if ((ret = CDB___os_seek(dbp->dbenv, \
00034  fhp, (dbp)->pgsize, pgno, 0, 0, DB_OS_SEEK_SET)) != 0) \
00035  goto err; \
00036  if ((ret = CDB___os_read(dbp->dbenv, \
00037  fhp, page, (dbp)->pgsize, &n)) != 0) \
00038  goto err; \
00039 }
00040 #define PUT_PAGE(dbp, fhp, pgno, page) { \
00041  if ((ret = CDB___os_seek(dbp->dbenv, \
00042  fhp, (dbp)->pgsize, pgno, 0, 0, DB_OS_SEEK_SET)) != 0) \
00043  goto err; \
00044  if ((ret = CDB___os_write(dbp->dbenv, \
00045  fhp, page, (dbp)->pgsize, &n)) != 0) \
00046  goto err; \
00047 }
00048 
00049 /*
00050  * CDB___db_31_offdup --
00051  * Convert 3.0 off-page duplicates to 3.1 off-page duplicates.
00052  *
00053  * PUBLIC: int CDB___db_31_offdup __P((DB *, char *, DB_FH *, int, db_pgno_t *));
00054  */
00055 int
00056 CDB___db_31_offdup(dbp, real_name, fhp, sorted, pgnop)
00057 DB *dbp;
00058 char *real_name;
00059 DB_FH *fhp;
00060 int sorted;
00061 db_pgno_t *pgnop;
00062 {
00063 PAGE *ipage, *page;
00064 db_indx_t indx;
00065 db_pgno_t cur_cnt, i, next_cnt, pgno, *pgno_cur, pgno_last;
00066 db_pgno_t *pgno_next, pgno_max, *tmp;
00067 db_recno_t nrecs;
00068 size_t n;
00069 int level, nomem, ret;
00070 
00071 ipage = page = NULL;
00072 pgno_cur = pgno_next = NULL;
00073 
00074 /* Allocate room to hold a page. */
00075 if ((ret = CDB___os_malloc(dbp->dbenv, dbp->pgsize, NULL, &page)) != 0)
00076 goto err;
00077 
00078 /*
00079  * Walk the chain of 3.0 off-page duplicates. Each one is converted
00080  * in place to a 3.1 off-page duplicate page. If the duplicates are
00081  * sorted, they are converted to a Btree leaf page, otherwise to a
00082  * Recno leaf page.
00083  */
00084 for (nrecs = 0, cur_cnt = pgno_max = 0,
00085 pgno = *pgnop; pgno != PGNO_INVALID;) {
00086 if (pgno_max == cur_cnt) {
00087 pgno_max += 20;
00088 if ((ret = CDB___os_realloc(dbp->dbenv, pgno_max *
00089 sizeof(db_pgno_t), NULL, &pgno_cur)) != 0)
00090 goto err;
00091 }
00092 pgno_cur[cur_cnt++] = pgno;
00093 
00094 GET_PAGE(dbp, fhp, pgno, page);
00095 nrecs += NUM_ENT(page);
00096 LEVEL(page) = LEAFLEVEL;
00097 TYPE_SET(page, sorted ? P_LDUP : P_LRECNO);
00098 /*
00099  * !!!
00100  * DB didn't zero the LSNs on off-page duplicates pages.
00101  */
00102 ZERO_LSN(LSN(page));
00103 PUT_PAGE(dbp, fhp, pgno, page);
00104 
00105 pgno = NEXT_PGNO(page);
00106 }
00107 
00108 /* If we only have a single page, it's easy. */
00109 if (cur_cnt > 1) {
00110 /*
00111  * pgno_cur is the list of pages we just converted. We're
00112  * going to walk that list, but we'll need to create a new
00113  * list while we do so.
00114  */
00115 if ((ret = CDB___os_malloc(dbp->dbenv,
00116 cur_cnt * sizeof(db_pgno_t), NULL, &pgno_next)) != 0)
00117 goto err;
00118 
00119 /* Figure out where we can start allocating new pages. */
00120 if ((ret = CDB___db_lastpgno(dbp, real_name, fhp, &pgno_last)) != 0)
00121 goto err;
00122 
00123 /* Allocate room for an internal page. */
00124 if ((ret = CDB___os_malloc(dbp->dbenv,
00125 dbp->pgsize, NULL, &ipage)) != 0)
00126 goto err;
00127 PGNO(ipage) = PGNO_INVALID;
00128 }
00129 
00130 /*
00131  * Repeatedly walk the list of pages, building internal pages, until
00132  * there's only one page at a level.
00133  */
00134 for (level = LEAFLEVEL + 1; cur_cnt > 1; ++level) {
00135 for (indx = 0, i = next_cnt = 0; i < cur_cnt;) {
00136 if (indx == 0) {
00137 P_INIT(ipage, dbp->pgsize, pgno_last,
00138 PGNO_INVALID, PGNO_INVALID,
00139 level, sorted ? P_IBTREE : P_IRECNO, 0);
00140 ZERO_LSN(LSN(ipage));
00141 
00142 pgno_next[next_cnt++] = pgno_last++;
00143 }
00144 
00145 GET_PAGE(dbp, fhp, pgno_cur[i], page);
00146 
00147 /*
00148  * If the duplicates are sorted, put the first item on
00149  * the lower-level page onto a Btree internal page. If
00150  * the duplicates are not sorted, create an internal
00151  * Recno structure on the page. If either case doesn't
00152  * fit, push out the current page and start a new one.
00153  */
00154 nomem = 0;
00155 if (sorted) {
00156 if ((ret = __db_build_bi(
00157 dbp, fhp, ipage, page, indx, &nomem)) != 0)
00158 goto err;
00159 } else
00160 if ((ret = __db_build_ri(
00161 dbp, fhp, ipage, page, indx, &nomem)) != 0)
00162 goto err;
00163 if (nomem) {
00164 indx = 0;
00165 PUT_PAGE(dbp, fhp, PGNO(ipage), ipage);
00166 } else {
00167 ++indx;
00168 ++NUM_ENT(ipage);
00169 ++i;
00170 }
00171 }
00172 
00173 /*
00174  * Push out the last internal page. Set the top-level record
00175  * count if we've reached the top.
00176  */
00177 if (next_cnt == 1)
00178 RE_NREC_SET(ipage, nrecs);
00179 PUT_PAGE(dbp, fhp, PGNO(ipage), ipage);
00180 
00181 /* Swap the current and next page number arrays. */
00182 cur_cnt = next_cnt;
00183 tmp = pgno_cur;
00184 pgno_cur = pgno_next;
00185 pgno_next = tmp;
00186 }
00187 
00188 *pgnop = pgno_cur[0];
00189 
00190 err: if (pgno_cur != NULL)
00191 CDB___os_free(pgno_cur, 0);
00192 if (pgno_next != NULL)
00193 CDB___os_free(pgno_next, 0);
00194 if (ipage != NULL)
00195 CDB___os_free(ipage, dbp->pgsize);
00196 if (page != NULL)
00197 CDB___os_free(page, dbp->pgsize);
00198 
00199 return (ret);
00200 }
00201 
00202 /*
00203  * __db_build_bi --
00204  * Build a BINTERNAL entry for a parent page.
00205  */
00206 static int
00207 __db_build_bi(dbp, fhp, ipage, page, indx, nomemp)
00208 DB *dbp;
00209 DB_FH *fhp;
00210 PAGE *ipage, *page;
00211 u_int32_t indx;
00212 int *nomemp;
00213 {
00214 BINTERNAL bi, *child_bi;
00215 BKEYDATA *child_bk;
00216 u_int8_t *p;
00217 int ret;
00218 
00219 switch (TYPE(page)) {
00220 case P_IBTREE:
00221 child_bi = GET_BINTERNAL(page, 0);
00222 if (P_FREESPACE(ipage) < BINTERNAL_PSIZE(child_bi->len)) {
00223 *nomemp = 1;
00224 return (0);
00225 }
00226 ipage->inp[indx] =
00227 HOFFSET(ipage) -= BINTERNAL_SIZE(child_bi->len);
00228 p = P_ENTRY(ipage, indx);
00229 
00230 bi.len = child_bi->len;
00231 B_TSET(bi.type, child_bi->type, 0);
00232 bi.pgno = PGNO(page);
00233 bi.nrecs = CDB___bam_total(page);
00234 memcpy(p, &bi, SSZA(BINTERNAL, data));
00235 p += SSZA(BINTERNAL, data);
00236 memcpy(p, child_bi->data, child_bi->len);
00237 
00238 /* Increment the overflow ref count. */
00239 if (B_TYPE(child_bi->type) == B_OVERFLOW)
00240 if ((ret = __db_up_ovref(dbp, fhp,
00241 ((BOVERFLOW *)(child_bi->data))->pgno)) != 0)
00242 return (ret);
00243 break;
00244 case P_LDUP:
00245 child_bk = GET_BKEYDATA(page, 0);
00246 switch (B_TYPE(child_bk->type)) {
00247 case B_KEYDATA:
00248 if (P_FREESPACE(ipage) <
00249 BINTERNAL_PSIZE(child_bk->len)) {
00250 *nomemp = 1;
00251 return (0);
00252 }
00253 ipage->inp[indx] =
00254 HOFFSET(ipage) -= BINTERNAL_SIZE(child_bk->len);
00255 p = P_ENTRY(ipage, indx);
00256 
00257 bi.len = child_bk->len;
00258 B_TSET(bi.type, child_bk->type, 0);
00259 bi.pgno = PGNO(page);
00260 bi.nrecs = CDB___bam_total(page);
00261 memcpy(p, &bi, SSZA(BINTERNAL, data));
00262 p += SSZA(BINTERNAL, data);
00263 memcpy(p, child_bk->data, child_bk->len);
00264 break;
00265 case B_OVERFLOW:
00266 if (P_FREESPACE(ipage) <
00267 BINTERNAL_PSIZE(BOVERFLOW_SIZE)) {
00268 *nomemp = 1;
00269 return (0);
00270 }
00271 ipage->inp[indx] =
00272 HOFFSET(ipage) -= BINTERNAL_SIZE(BOVERFLOW_SIZE);
00273 p = P_ENTRY(ipage, indx);
00274 
00275 bi.len = BOVERFLOW_SIZE;
00276 B_TSET(bi.type, child_bk->type, 0);
00277 bi.pgno = PGNO(page);
00278 bi.nrecs = CDB___bam_total(page);
00279 memcpy(p, &bi, SSZA(BINTERNAL, data));
00280 p += SSZA(BINTERNAL, data);
00281 memcpy(p, child_bk, BOVERFLOW_SIZE);
00282 
00283 /* Increment the overflow ref count. */
00284 if ((ret = __db_up_ovref(dbp, fhp,
00285 ((BOVERFLOW *)child_bk)->pgno)) != 0)
00286 return (ret);
00287 break;
00288 default:
00289 return (CDB___db_pgfmt(dbp, PGNO(page)));
00290 }
00291 break;
00292 default:
00293 return (CDB___db_pgfmt(dbp, PGNO(page)));
00294 }
00295 
00296 return (0);
00297 }
00298 
00299 /*
00300  * __db_build_ri --
00301  * Build a RINTERNAL entry for an internal parent page.
00302  */
00303 static int
00304 __db_build_ri(dbp, fhp, ipage, page, indx, nomemp)
00305 DB *dbp;
00306 DB_FH *fhp;
00307 PAGE *ipage, *page;
00308 u_int32_t indx;
00309 int *nomemp;
00310 {
00311 RINTERNAL ri;
00312 
00313 COMPQUIET(dbp, NULL);
00314 COMPQUIET(fhp, NULL);
00315 
00316 if (P_FREESPACE(ipage) < RINTERNAL_PSIZE) {
00317 *nomemp = 1;
00318 return (0);
00319 }
00320 
00321 ri.pgno = PGNO(page);
00322 ri.nrecs = CDB___bam_total(page);
00323 ipage->inp[indx] = HOFFSET(ipage) -= RINTERNAL_SIZE;
00324 memcpy(P_ENTRY(ipage, indx), &ri, RINTERNAL_SIZE);
00325 
00326 return (0);
00327 }
00328 
00329 /*
00330  * __db_up_ovref --
00331  * Increment/decrement the reference count on an overflow page.
00332  */
00333 static int
00334 __db_up_ovref(dbp, fhp, pgno)
00335 DB *dbp;
00336 DB_FH *fhp;
00337 db_pgno_t pgno;
00338 {
00339 PAGE *page;
00340 size_t n;
00341 int ret;
00342 
00343 /* Allocate room to hold a page. */
00344 if ((ret = CDB___os_malloc(dbp->dbenv, dbp->pgsize, NULL, &page)) != 0)
00345 return (ret);
00346 
00347 GET_PAGE(dbp, fhp, pgno, page);
00348 ++OV_REF(page);
00349 PUT_PAGE(dbp, fhp, pgno, page);
00350 
00351 err: CDB___os_free(page, dbp->pgsize);
00352 
00353 return (ret);
00354 }