Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Changes In Branch small_stack Excluding Merge-Ins
This is equivalent to a diff from e6c8df3bb7 to f93a54d0ba
|
2010-10-05
| ||
| 03:29 | Merge the small-stack changes into the trunk. This completes the fix for ticket [2a1e8e3c4b0b39e08fdde] check-in: b8f134bbbb user: drh tags: trunk | |
| 03:24 | Fix issues with the prior commit on this branch. The small-stack non-recursive implementation appears to be working. Ticket [2a1e8e3c4b0b39e08fdde]. Closed-Leaf check-in: f93a54d0ba user: drh tags: small_stack | |
| 02:46 | An attempt to reduce the depth of recursion in order to run better on systems with limited stack spack. Ticket [2a1e8e3c4b0b39e08fdde0]. This check-in compiles and runs but has issues. check-in: 9664989c0f user: drh tags: small_stack | |
| 00:40 | Fix HTML typo in qandc.wiki. Ticket [cee1b58990e81] check-in: e6c8df3bb7 user: drh tags: trunk | |
|
2010-10-03
| ||
| 23:31 | Make the R card of manifests truely optional. It is always generated on manifests created by Fossil itself, but 3rd party import tools might choose to omit the R card as a simplification. Ticket [a32ff1eddb6ac1f499]. check-in: aab38ef02f user: drh tags: trunk | |
Changes to src/content.c.
20 20 #include "config.h" 21 21 #include "content.h" 22 22 #include <assert.h> 23 23 24 24 /* 25 25 ** Macros for debugging 26 26 */ 27 -#if 0 27 +#if 1 28 28 # define CONTENT_TRACE(X) printf X; 29 29 #else 30 30 # define CONTENT_TRACE(X) 31 31 #endif 32 32 33 33 /* 34 34 ** The artifact retrival cache 35 35 */ 36 -#define MX_CACHE_CNT 50 /* Maximum number of positive cache entries */ 37 -#define EXPELL_INTERVAL 5 /* How often to expell from a full cache */ 38 36 static struct { 39 - int n; /* Current number of positive cache entries */ 37 + i64 szTotal; /* Total size of all entries in the cache */ 38 + int n; /* Current number of eache entries */ 39 + int nAlloc; /* Number of slots allocated in a[] */ 40 40 int nextAge; /* Age counter for implementing LRU */ 41 41 int skipCnt; /* Used to limit entries expelled from cache */ 42 - struct { /* One instance of this for each cache entry */ 42 + struct cacheLine { /* One instance of this for each cache entry */ 43 43 int rid; /* Artifact id */ 44 44 int age; /* Age. Newer is larger */ 45 45 Blob content; /* Content of the artifact */ 46 - } a[MX_CACHE_CNT]; /* The positive cache */ 46 + } *a; /* The positive cache */ 47 + Bag inCache; /* Set of artifacts currently in cache */ 47 48 48 49 /* 49 50 ** The missing artifact cache. 50 51 ** 51 52 ** Artifacts whose record ID are in missingCache cannot be retrieved 52 53 ** either because they are phantoms or because they are a delta that 53 54 ** depends on a phantom. Artifacts whose content we are certain is ................................................................................ 54 55 ** available are in availableCache. If an artifact is in neither cache 55 56 ** then its current availablity is unknown. 56 57 */ 57 58 Bag missing; /* Cache of artifacts that are incomplete */ 58 59 Bag available; /* Cache of artifacts that are complete */ 59 60 } contentCache; 60 61 62 +/* 63 +** Remove the oldest element from the content cache 64 +*/ 65 +static void content_cache_expire_oldest(void){ 66 + int i; 67 + int mnAge = contentCache.nextAge; 68 + int mn = -1; 69 + for(i=0; i<contentCache.n; i++){ 70 + if( contentCache.a[i].age<mnAge ){ 71 + mnAge = contentCache.a[i].age; 72 + mn = i; 73 + } 74 + } 75 + if( mn>=0 ){ 76 + bag_remove(&contentCache.inCache, contentCache.a[mn].rid); 77 + contentCache.szTotal -= blob_size(&contentCache.a[mn].content); 78 + blob_reset(&contentCache.a[mn].content); 79 + contentCache.n--; 80 + contentCache.a[mn] = contentCache.a[contentCache.n]; 81 + } 82 +} 83 + 84 +/* 85 +** Add an entry to the content cache 86 +*/ 87 +void content_cache_insert(int rid, Blob *pBlob){ 88 + struct cacheLine *p; 89 + if( contentCache.n>500 || contentCache.szTotal>50000000 ){ 90 + content_cache_expire_oldest(); 91 + } 92 + if( contentCache.n>=contentCache.nAlloc ){ 93 + contentCache.nAlloc = contentCache.nAlloc*2 + 10; 94 + contentCache.a = realloc(contentCache.a, 95 + contentCache.nAlloc*sizeof(contentCache.a[0])); 96 + if( contentCache.a==0 ) fossil_panic("out of memory"); 97 + } 98 + p = &contentCache.a[contentCache.n++]; 99 + p->rid = rid; 100 + p->age = contentCache.nextAge++; 101 + contentCache.szTotal += blob_size(pBlob); 102 + p->content = *pBlob; 103 + blob_zero(pBlob); 104 + bag_insert(&contentCache.inCache, rid); 105 +} 61 106 62 107 /* 63 108 ** Clear the content cache. 64 109 */ 65 110 void content_clear_cache(void){ 66 111 int i; 67 112 for(i=0; i<contentCache.n; i++){ 68 113 blob_reset(&contentCache.a[i].content); 69 114 } 70 115 bag_clear(&contentCache.missing); 71 116 bag_clear(&contentCache.available); 117 + bag_clear(&contentCache.inCache); 72 118 contentCache.n = 0; 119 + contentCache.szTotal = 0; 73 120 } 74 121 75 122 /* 76 123 ** Return the srcid associated with rid. Or return 0 if rid is 77 124 ** original content and not a delta. 78 125 */ 79 126 static int findSrcid(int rid){ ................................................................................ 93 140 /* 94 141 ** Check to see if content is available for artifact "rid". Return 95 142 ** true if it is. Return false if rid is a phantom or depends on 96 143 ** a phantom. 97 144 */ 98 145 int content_is_available(int rid){ 99 146 int srcid; 100 - if( bag_find(&contentCache.missing, rid) ){ 101 - return 0; 102 - } 103 - if( bag_find(&contentCache.available, rid) ){ 104 - return 1; 105 - } 106 - if( db_int(-1, "SELECT size FROM blob WHERE rid=%d", rid)<0 ){ 107 - bag_insert(&contentCache.missing, rid); 108 - return 0; 109 - } 110 - srcid = findSrcid(rid); 111 - if( srcid==0 ){ 112 - bag_insert(&contentCache.available, rid); 113 - return 1; 114 - } 115 - if( content_is_available(srcid) ){ 116 - bag_insert(&contentCache.available, rid); 117 - return 1; 118 - }else{ 119 - bag_insert(&contentCache.missing, rid); 120 - return 0; 121 - } 147 + int depth = 0; /* Limit to recursion depth */ 148 + while( depth++ < 10000000 ){ 149 + if( bag_find(&contentCache.missing, rid) ){ 150 + return 0; 151 + } 152 + if( bag_find(&contentCache.available, rid) ){ 153 + return 1; 154 + } 155 + if( db_int(-1, "SELECT size FROM blob WHERE rid=%d", rid)<0 ){ 156 + bag_insert(&contentCache.missing, rid); 157 + return 0; 158 + } 159 + srcid = findSrcid(rid); 160 + if( srcid==0 ){ 161 + bag_insert(&contentCache.available, rid); 162 + return 1; 163 + } 164 + rid = srcid; 165 + } 166 + fossil_panic("delta-loop in repository"); 167 + return 0; 122 168 } 123 169 124 170 /* 125 171 ** Mark artifact rid as being available now. Update the cache to 126 172 ** show that everything that was formerly unavailable because rid 127 173 ** was missing is now available. 128 174 */ ................................................................................ 161 207 blob_uncompress(pBlob, pBlob); 162 208 rc = 1; 163 209 } 164 210 db_reset(&q); 165 211 return rc; 166 212 } 167 213 168 - 169 214 /* 170 215 ** Extract the content for ID rid and put it into the 171 216 ** uninitialized blob. Return 1 on success. If the record 172 217 ** is a phantom, zero pBlob and return 0. 173 218 */ 174 219 int content_get(int rid, Blob *pBlob){ 175 - Blob src; 176 - int srcid; 177 - int rc = 0; 220 + int rc; 178 221 int i; 179 - static Bag inProcess; 222 + int nextRid; 180 223 181 224 assert( g.repositoryOpen ); 182 225 blob_zero(pBlob); 183 226 if( rid==0 ) return 0; 184 227 185 228 /* Early out if we know the content is not available */ 186 229 if( bag_find(&contentCache.missing, rid) ){ 187 - CONTENT_TRACE(("%*smiss from cache: %d\n", 188 - bag_count(&inProcess), "", rid)) 189 230 return 0; 190 231 } 191 232 192 233 /* Look for the artifact in the cache first */ 193 - for(i=0; i<contentCache.n; i++){ 194 - if( contentCache.a[i].rid==rid ){ 195 - *pBlob = contentCache.a[i].content; 196 - blob_zero(&contentCache.a[i].content); 197 - contentCache.n--; 198 - if( i<contentCache.n ){ 199 - contentCache.a[i] = contentCache.a[contentCache.n]; 234 + if( bag_find(&contentCache.inCache, rid) ){ 235 + for(i=0; i<contentCache.n; i++){ 236 + if( contentCache.a[i].rid==rid ){ 237 + blob_copy(pBlob, &contentCache.a[i].content); 238 + contentCache.a[i].age = contentCache.nextAge++; 239 + return 1; 200 240 } 201 - CONTENT_TRACE(("%*scache: %d\n", 202 - bag_count(&inProcess), "", rid)) 203 - return 1; 204 241 } 205 242 } 206 243 207 - /* See if we need to apply a delta to find this artifact */ 208 - srcid = findSrcid(rid); 209 - CONTENT_TRACE(("%*ssearching for %d. Need %d.\n", 210 - bag_count(&inProcess), "", rid, srcid)) 211 - 212 - 213 - if( srcid ){ 214 - /* Yes, a delta is required */ 215 - if( bag_find(&inProcess, srcid) ){ 216 - db_multi_exec( 217 - "UPDATE blob SET content=NULL, size=-1 WHERE rid=%d;" 218 - "DELETE FROM delta WHERE rid=%d;" 219 - "INSERT OR IGNORE INTO phantom VALUES(%d);", 220 - srcid, srcid, srcid 221 - ); 222 - blob_zero(pBlob); 223 - return 0; 244 + nextRid = findSrcid(rid); 245 + if( nextRid==0 ){ 246 + rc = content_of_blob(rid, pBlob); 247 + }else{ 248 + int n = 1; 249 + int nAlloc = 10; 250 + int *a = 0; 251 + int mx; 252 + Blob delta, next; 253 + 254 + a = malloc( sizeof(a[0])*nAlloc ); 255 + if( a==0 ) fossil_panic("out of memory"); 256 + a[0] = rid; 257 + a[1] = nextRid; 258 + n = 1; 259 + while( !bag_find(&contentCache.inCache, nextRid) 260 + && (nextRid = findSrcid(nextRid))>0 ){ 261 + n++; 262 + if( n>=nAlloc ){ 263 + nAlloc = nAlloc*2 + 10; 264 + a = realloc(a, nAlloc*sizeof(a[0])); 265 + if( a==0 ) fossil_panic("out of memory"); 266 + } 267 + a[n] = nextRid; 224 268 } 225 - bag_insert(&inProcess, srcid); 226 - 227 - if( content_get(srcid, &src) ){ 228 - Blob delta; 229 - if( content_of_blob(rid, &delta) ){ 230 - blob_init(pBlob,0,0); 231 - blob_delta_apply(&src, &delta, pBlob); 269 + mx = n; 270 + rc = content_get(a[n], pBlob); 271 + n--; 272 + while( rc && n>=0 ){ 273 + rc = content_of_blob(a[n], &delta); 274 + if( rc ){ 275 + blob_delta_apply(pBlob, &delta, &next); 232 276 blob_reset(&delta); 233 - rc = 1; 234 - } 235 - 236 - /* Save the srcid artifact in the cache */ 237 - if( contentCache.n<MX_CACHE_CNT ){ 238 - i = contentCache.n++; 239 - }else if( ((contentCache.skipCnt++)%EXPELL_INTERVAL)!=0 ){ 240 - i = -1; 241 - }else{ 242 - int j, best; 243 - best = contentCache.nextAge+1; 244 - i = -1; 245 - for(j=0; j<contentCache.n; j++){ 246 - if( contentCache.a[j].age<best ){ 247 - i = j; 248 - best = contentCache.a[j].age; 249 - } 277 + if( (mx-n)%8==0 ){ 278 + content_cache_insert(a[n+1], pBlob); 279 + }else{ 280 + blob_reset(pBlob); 250 281 } 251 - CONTENT_TRACE(("%*sexpell %d from cache\n", 252 - bag_count(&inProcess), "", contentCache.a[i].rid)) 253 - blob_reset(&contentCache.a[i].content); 282 + *pBlob = next; 254 283 } 255 - if( i>=0 ){ 256 - contentCache.a[i].content = src; 257 - contentCache.a[i].age = contentCache.nextAge++; 258 - contentCache.a[i].rid = srcid; 259 - CONTENT_TRACE(("%*sadd %d to cache\n", 260 - bag_count(&inProcess), "", srcid)) 261 - }else{ 262 - blob_reset(&src); 263 - } 284 + n--; 264 285 } 265 - bag_remove(&inProcess, srcid); 266 - }else{ 267 - /* No delta required. Read content directly from the database */ 268 - if( content_of_blob(rid, pBlob) ){ 269 - rc = 1; 270 - } 286 + free(a); 287 + if( !rc ) blob_reset(pBlob); 271 288 } 272 289 if( rc==0 ){ 273 290 bag_insert(&contentCache.missing, rid); 274 291 }else{ 275 292 bag_insert(&contentCache.available, rid); 276 293 } 277 294 return rc; ................................................................................ 318 335 blob_write_to_file(&content, zFile); 319 336 } 320 337 321 338 /* 322 339 ** When a record is converted from a phantom to a real record, 323 340 ** if that record has other records that are derived by delta, 324 341 ** then call manifest_crosslink() on those other records. 342 +** 343 +** Tail recursion is used to minimize stack depth. 325 344 */ 326 345 void after_dephantomize(int rid, int linkFlag){ 327 346 Stmt q; 328 - int prevTid = 0; 329 - 330 - /* The prevTid variable is used to delay invoking this routine 331 - ** recursively, if possible, until after the query has finalized, 332 - ** in order to avoid having an excessive number of prepared statements. 333 - ** This is most effective in the common case where the query returns 334 - ** just one row. 335 - */ 336 - db_prepare(&q, "SELECT rid FROM delta WHERE srcid=%d", rid); 337 - while( db_step(&q)==SQLITE_ROW ){ 338 - int tid = db_column_int(&q, 0); 339 - if( prevTid ) after_dephantomize(prevTid, 1); 340 - prevTid = tid; 341 - } 342 - db_finalize(&q); 343 - if( prevTid ) after_dephantomize(prevTid, 1); 344 - if( linkFlag ){ 345 - Blob content; 346 - content_get(rid, &content); 347 - manifest_crosslink(rid, &content); 348 - blob_reset(&content); 349 - } 347 + int nChildAlloc = 0; 348 + int *aChild = 0; 349 + 350 + while( rid ){ 351 + int nChildUsed = 0; 352 + int i; 353 + if( linkFlag ){ 354 + Blob content; 355 + content_get(rid, &content); 356 + manifest_crosslink(rid, &content); 357 + blob_reset(&content); 358 + } 359 + db_prepare(&q, "SELECT rid FROM delta WHERE srcid=%d", rid); 360 + while( db_step(&q)==SQLITE_ROW ){ 361 + int child = db_column_int(&q, 0); 362 + if( nChildUsed>=nChildAlloc ){ 363 + nChildAlloc = nChildAlloc*2 + 10; 364 + aChild = realloc(aChild, nChildAlloc*sizeof(aChild)); 365 + if( aChild==0 ) fossil_panic("out of memory"); 366 + } 367 + aChild[nChildUsed++] = child; 368 + } 369 + db_finalize(&q); 370 + for(i=1; i<nChildUsed; i++){ 371 + after_dephantomize(aChild[i], 1); 372 + } 373 + rid = nChildUsed>0 ? aChild[0] : 0; 374 + linkFlag = 1; 375 + } 376 + free(aChild); 350 377 } 351 378 352 379 /* 353 380 ** Write content into the database. Return the record ID. If the 354 381 ** content is already in the database, just return the record ID. 355 382 ** 356 383 ** If srcId is specified, then pBlob is delta content from
Changes to src/rebuild.c.
119 119 static void rebuild_step(int rid, int size, Blob *pBase){ 120 120 static Stmt q1; 121 121 Bag children; 122 122 Blob copy; 123 123 Blob *pUse; 124 124 int nChild, i, cid; 125 125 126 - /* Fix up the "blob.size" field if needed. */ 127 - if( size!=blob_size(pBase) ){ 128 - db_multi_exec( 129 - "UPDATE blob SET size=%d WHERE rid=%d", blob_size(pBase), rid 130 - ); 131 - } 132 - 133 - /* Find all children of artifact rid */ 134 - db_static_prepare(&q1, "SELECT rid FROM delta WHERE srcid=:rid"); 135 - db_bind_int(&q1, ":rid", rid); 136 - bag_init(&children); 137 - while( db_step(&q1)==SQLITE_ROW ){ 138 - int cid = db_column_int(&q1, 0); 139 - if( !bag_find(&bagDone, cid) ){ 140 - bag_insert(&children, cid); 141 - } 142 - } 143 - nChild = bag_count(&children); 144 - db_reset(&q1); 145 - 146 - /* Crosslink the artifact */ 147 - if( nChild==0 ){ 148 - pUse = pBase; 149 - }else{ 150 - blob_copy(©, pBase); 151 - pUse = © 152 - } 153 - if( zFNameFormat==0 ){ 154 - /* We are doing "fossil rebuild" */ 155 - manifest_crosslink(rid, pUse); 156 - }else{ 157 - /* We are doing "fossil deconstruct" */ 158 - char *zUuid = db_text(0, "SELECT uuid FROM blob WHERE rid=%d", rid); 159 - char *zFile = mprintf(zFNameFormat, zUuid, zUuid+prefixLength); 160 - blob_write_to_file(pUse,zFile); 161 - free(zFile); 162 - free(zUuid); 163 - } 164 - blob_reset(pUse); 165 - rebuild_step_done(rid); 166 - 167 - /* Call all children recursively */ 168 - for(cid=bag_first(&children), i=1; cid; cid=bag_next(&children, cid), i++){ 169 - Stmt q2; 170 - int sz; 171 - if( nChild==i ){ 126 + while( rid>0 ){ 127 + 128 + /* Fix up the "blob.size" field if needed. */ 129 + if( size!=blob_size(pBase) ){ 130 + db_multi_exec( 131 + "UPDATE blob SET size=%d WHERE rid=%d", blob_size(pBase), rid 132 + ); 133 + } 134 + 135 + /* Find all children of artifact rid */ 136 + db_static_prepare(&q1, "SELECT rid FROM delta WHERE srcid=:rid"); 137 + db_bind_int(&q1, ":rid", rid); 138 + bag_init(&children); 139 + while( db_step(&q1)==SQLITE_ROW ){ 140 + int cid = db_column_int(&q1, 0); 141 + if( !bag_find(&bagDone, cid) ){ 142 + bag_insert(&children, cid); 143 + } 144 + } 145 + nChild = bag_count(&children); 146 + db_reset(&q1); 147 + 148 + /* Crosslink the artifact */ 149 + if( nChild==0 ){ 172 150 pUse = pBase; 173 151 }else{ 174 152 blob_copy(©, pBase); 175 153 pUse = © 176 154 } 177 - db_prepare(&q2, "SELECT content, size FROM blob WHERE rid=%d", cid); 178 - if( db_step(&q2)==SQLITE_ROW && (sz = db_column_int(&q2,1))>=0 ){ 179 - Blob delta; 180 - db_ephemeral_blob(&q2, 0, &delta); 181 - blob_uncompress(&delta, &delta); 182 - blob_delta_apply(pUse, &delta, pUse); 183 - blob_reset(&delta); 184 - db_finalize(&q2); 185 - rebuild_step(cid, sz, pUse); 155 + if( zFNameFormat==0 ){ 156 + /* We are doing "fossil rebuild" */ 157 + manifest_crosslink(rid, pUse); 186 158 }else{ 187 - db_finalize(&q2); 188 - blob_reset(pUse); 159 + /* We are doing "fossil deconstruct" */ 160 + char *zUuid = db_text(0, "SELECT uuid FROM blob WHERE rid=%d", rid); 161 + char *zFile = mprintf(zFNameFormat, zUuid, zUuid+prefixLength); 162 + blob_write_to_file(pUse,zFile); 163 + free(zFile); 164 + free(zUuid); 165 + } 166 + blob_reset(pUse); 167 + rebuild_step_done(rid); 168 + 169 + /* Call all children recursively */ 170 + rid = 0; 171 + for(cid=bag_first(&children), i=1; cid; cid=bag_next(&children, cid), i++){ 172 + Stmt q2; 173 + int sz; 174 + db_prepare(&q2, "SELECT content, size FROM blob WHERE rid=%d", cid); 175 + if( db_step(&q2)==SQLITE_ROW && (sz = db_column_int(&q2,1))>=0 ){ 176 + Blob delta, next; 177 + db_ephemeral_blob(&q2, 0, &delta); 178 + blob_uncompress(&delta, &delta); 179 + blob_delta_apply(pBase, &delta, &next); 180 + blob_reset(&delta); 181 + db_finalize(&q2); 182 + if( i<nChild ){ 183 + rebuild_step(cid, sz, &next); 184 + }else{ 185 + /* Tail recursion */ 186 + rid = cid; 187 + size = sz; 188 + blob_reset(pBase); 189 + *pBase = next; 190 + } 191 + }else{ 192 + db_finalize(&q2); 193 + blob_reset(pBase); 194 + } 189 195 } 196 + bag_clear(&children); 190 197 } 191 - bag_clear(&children); 192 198 } 193 199 194 200 /* 195 201 ** Check to see if the "sym-trunk" tag exists. If not, create it 196 202 ** and attach it to the very first check-in. 197 203 */ 198 204 static void rebuild_tag_trunk(void){
Changes to src/xfer.c.
117 117 blob_zero(&hash); 118 118 blob_extract(pXfer->pIn, n, &content); 119 119 if( uuid_is_shunned(blob_str(&pXfer->aToken[1])) ){ 120 120 /* Ignore files that have been shunned */ 121 121 return; 122 122 } 123 123 if( pXfer->nToken==4 ){ 124 - Blob src; 124 + Blob src, next; 125 125 srcid = rid_from_uuid(&pXfer->aToken[2], 1); 126 126 if( content_get(srcid, &src)==0 ){ 127 127 rid = content_put(&content, blob_str(&pXfer->aToken[1]), srcid); 128 128 pXfer->nDanglingFile++; 129 129 db_multi_exec("DELETE FROM phantom WHERE rid=%d", rid); 130 130 content_make_public(rid); 131 131 return; 132 132 } 133 133 pXfer->nDeltaRcvd++; 134 - blob_delta_apply(&src, &content, &content); 134 + blob_delta_apply(&src, &content, &next); 135 135 blob_reset(&src); 136 + blob_reset(&content); 137 + content = next; 136 138 }else{ 137 139 pXfer->nFileRcvd++; 138 140 } 139 141 sha1sum_blob(&content, &hash); 140 142 if( !blob_eq_str(&pXfer->aToken[1], blob_str(&hash), -1) ){ 141 143 blob_appendf(&pXfer->err, "content does not match sha1 hash"); 142 144 }