From 9c7e44cddd76c19d8ac034dcce2da1ed978a6f02 Mon Sep 17 00:00:00 2001
From: drh <drh@noemail.net>
Date: Thu, 14 Feb 2019 15:27:12 +0000
Subject: [PATCH] Improved oversized cell detection when updating ptrmap pages
 in balance_nonroot().

FossilOrigin-Name: aa61435a4c3800f023788081c1342ad6a05a41449a424fa6c039d5ca46072256
---
 manifest          |  14 +++++++-------
 manifest.uuid     |   2 +-
 src/btree.c       |  23 +++++++++++++++--------
 test/fuzzdata8.db | Bin 975872 -> 980992 bytes
 4 files changed, 23 insertions(+), 16 deletions(-)

diff --git a/manifest b/manifest
index c48ba75e83..31ec0424b9 100644
--- a/manifest
+++ b/manifest
@@ -1,5 +1,5 @@
-C Ensure\sthat\sthe\snProgressLimit\svariable\sis\salways\sinitialized\sin\nsqlite3VdbeExec(),\seven\sif\sthe\sroutine\sjumps\sto\sits\sexit\sprocessing\searly.
-D 2019-02-12T22:58:32.377
+C Improved\soversized\scell\sdetection\swhen\supdating\sptrmap\spages\sin\nbalance_nonroot().
+D 2019-02-14T15:27:12.650
 F .fossil-settings/empty-dirs dbb81e8fc0401ac46a1491ab34a7f2c7c0452f2f06b54ebb845d024ca8283ef1
 F .fossil-settings/ignore-glob 35175cdfcf539b2318cb04a9901442804be81cd677d8b889fcc9149c21f239ea
 F Makefile.in 178d8eb6840771149cee40b322d1b3be30d330198c522c903c1b66fb5a1bfca4
@@ -455,7 +455,7 @@ F src/auth.c 0fac71038875693a937e506bceb492c5f136dd7b1249fbd4ae70b4e8da14f9df
 F src/backup.c 78d3cecfbe28230a3a9a1793e2ead609f469be43e8f486ca996006be551857ab
 F src/bitvec.c 17ea48eff8ba979f1f5b04cc484c7bb2be632f33
 F src/btmutex.c 8acc2f464ee76324bf13310df5692a262b801808984c1b79defb2503bbafadb6
-F src/btree.c 1336cc1670ec9ab93c097ae0c087480f501fd9c7157be0457b2b04e67a06a377
+F src/btree.c 161b6a57b91d160065e512a4d0be180e402a16a059034a380cbdc2411924f8ac
 F src/btree.h 63b94fb38ce571c15eb6a3661815561b501d23d5948b2d1e951fbd7a2d04e8d3
 F src/btreeInt.h 6111c15868b90669f79081039d19e7ea8674013f907710baa3c814dc3f8bfd3f
 F src/build.c b0a9ee5b551afbc8357a68eb30693973300daf845c8c0e564f672d9b3fdeec56
@@ -992,7 +992,7 @@ F test/fuzzdata4.db b502c7d5498261715812dd8b3c2005bad08b3a26e6489414bd13926cd3e4
 F test/fuzzdata5.db e35f64af17ec48926481cfaf3b3855e436bd40d1cfe2d59a9474cb4b748a52a5
 F test/fuzzdata6.db 92a80e4afc172c24f662a10a612d188fb272de4a9bd19e017927c95f737de6d7
 F test/fuzzdata7.db 3fc78e65dfe0be9df9e262075d5a335f18f627da47dfc691d1a7b822f34d4b99
-F test/fuzzdata8.db 19fcda3a879b840f8ff139701b116098be40c28c4fe1366e1fc813fb7afa7eea
+F test/fuzzdata8.db 267bc89b51f4f0fca01f80ff432ff9b26e65131e806c5ca20119dfc63dd47a90
 F test/fuzzer1.test 3d4c4b7e547aba5e5511a2991e3e3d07166cfbb8
 F test/fuzzer2.test a85ef814ce071293bce1ad8dffa217cbbaad4c14
 F test/fuzzerfault.test 8792cd77fd5bce765b05d0c8e01b9edcf8af8536
@@ -1804,7 +1804,7 @@ F vsixtest/vsixtest.tcl 6a9a6ab600c25a91a7acc6293828957a386a8a93
 F vsixtest/vsixtest.vcxproj.data 2ed517e100c66dc455b492e1a33350c1b20fbcdc
 F vsixtest/vsixtest.vcxproj.filters 37e51ffedcdb064aad6ff33b6148725226cd608e
 F vsixtest/vsixtest_TemporaryKey.pfx e5b1b036facdb453873e7084e1cae9102ccc67a0
-P 68cce272e7f7cbc0c319ee8b7ff674d652cb1e95e903d99d848c41dff2b5d304
-R 1dd11fa4b345d5a202cdf255a23d5245
+P 167b91df77fff1a84791f6ab5f72239b90475475be690a838248119b6dd312f0
+R 5fce60e5e60143c7168638176073d3e9
 U drh
-Z 5c1fab9a93beb29aa193da2ce5906eed
+Z 1127274df05b3c005a32360404b93266
diff --git a/manifest.uuid b/manifest.uuid
index 90a8aea4e5..c6a49cf8da 100644
--- a/manifest.uuid
+++ b/manifest.uuid
@@ -1 +1 @@
-167b91df77fff1a84791f6ab5f72239b90475475be690a838248119b6dd312f0
\ No newline at end of file
+aa61435a4c3800f023788081c1342ad6a05a41449a424fa6c039d5ca46072256
\ No newline at end of file
diff --git a/src/btree.c b/src/btree.c
index fbfc67a796..fe0112ced7 100644
--- a/src/btree.c
+++ b/src/btree.c
@@ -6817,8 +6817,13 @@ static void insertCell(
 ** are used and they point to the leaf pages only, and the ixNx value are:
 **
 **    ixNx[0] = Number of cells in Child-1.
-**    ixNx[1] = Number of cells in Child-1 and Child-2 + 1 for 1st divider.
-**    ixNx[2] = Number of cells in Child-1 and Child-2 + both divider cells
+**    ixNx[1] = Number of cells in Child-1 and Child-2.
+**    ixNx[2] = Total number of cells.
+**
+** Sometimes when deleting, a child page can have zero cells.  In those
+** cases, ixNx[] entries with higher indexes, and the corresponding apEnd[]
+** entries, shift down.  The end result is that each ixNx[] entry should
+** be larger than the previous
 */
 typedef struct CellArray CellArray;
 struct CellArray {
@@ -7747,6 +7752,9 @@ static int balance_nonroot(
     MemPage *p = apOld[i];
     b.apEnd[k] = p->aDataEnd;
     b.ixNx[k] = cntOld[i];
+    if( k && b.ixNx[k]==b.ixNx[k-1] ){
+      k--;  /* Omit b.ixNx[] entry for child pages with no cells */
+    }
     if( !leafData ){
       k++;
       b.apEnd[k] = pParent->aDataEnd;
@@ -7978,18 +7986,17 @@ static int balance_nonroot(
   if( ISAUTOVACUUM ){
     MemPage *pOld;
     MemPage *pNew = pOld = apNew[0];
-    u8 *aOld = pNew->aData;
     int cntOldNext = pNew->nCell + pNew->nOverflow;
-    int usableSize = pBt->usableSize;
     int iNew = 0;
     int iOld = 0;
 
     for(i=0; i<b.nCell; i++){
       u8 *pCell = b.apCell[i];
-      if( i==cntOldNext ){
-        pOld = (++iOld)<nNew ? apNew[iOld] : apOld[iOld];
+      while( i==cntOldNext ){
+        iOld++;
+        assert( iOld<nNew || iOld<nOld );
+        pOld = iOld<nNew ? apNew[iOld] : apOld[iOld];
         cntOldNext += pOld->nCell + pOld->nOverflow + !leafData;
-        aOld = pOld->aData;
       }
       if( i==cntNew[iNew] ){
         pNew = apNew[++iNew];
@@ -8004,7 +8011,7 @@ static int balance_nonroot(
       ** overflow cell), we can skip updating the pointer map entries.  */
       if( iOld>=nNew
        || pNew->pgno!=aPgno[iOld]
-       || !SQLITE_WITHIN(pCell,aOld,&aOld[usableSize])
+       || !SQLITE_WITHIN(pCell,pOld->aData,pOld->aDataEnd)
       ){
         if( !leafCorrection ){
           ptrmapPut(pBt, get4byte(pCell), PTRMAP_BTREE, pNew->pgno, &rc);
diff --git a/test/fuzzdata8.db b/test/fuzzdata8.db
index dfaf1cb468b36980aa7f591d7fada5907b3724f2..e81a9dea0a1b516ee462a804fe98ee55f59f2592 100644
GIT binary patch
delta 3629
zc-nQAdsI}_8o=k<=gc|t*yjie;+x?m7ZI3&K_CPfEftk`q~%Sm0Rb}~42g**!l-Gf
zAvnsXh5|{brHNW>H7#h>4Z{jrc5hjx-0NMrZnd<>y;j$*cONR7#pqt^`~KKx?{ELU
z=S)>+YSs1Bn&JLqbvoe<-5<-Zc5H%vtS;7WIa=5#8w!b_(@uD(;V*;;9)IfbEHLh!
zBfRQ1^8J_G2Cf_3GS_u(iR&$HJ=bg9BG)Buepx7T1J`rhnw{KAuBNQv%2C0UeKl8q
zTE$gZIakA1a5ZS1)3niP0xpD$z(wSu=OS^Dxfr+@xoGFi%xR*{F<5%dyqTT8hx!4w
z2TMa(OE?t)7w-fEHUc$ZYbuC!X|x(I%OGLNTjnwNMjBnFVfr&$I<)|{zG9v|AZ5PQ
zW}1_jY)_bHD@sYikRxV0Sh3wAt-+EE`Z-?TW%kgbq=Mq#7cPw?gV7pIMN}u!7|r59
zw7hGcONt9HKbnq0>oIc(wnoz&w2q*&v1Sr=VMDz+5QpANOT}c9)rzjO=85R~nI>Vw
z9<u|LSlWcSKT?}y)s_w2Khi+7PNsuJElF5))f|e}IGQX?%FfEloQXBd^r5(IncjjI
z<7gNrPocT^<r9X$!TFXcGqNXIBE!lGN+K=Ud6t6ow8(|nGn)*;tUX}Dyf20AcycNo
z;AbC~oS2ZDXtmpHwgh`}0y;LzLAdQdroresNBl7)o<`%kE&SrCOga#Y;^`1P`ig!S
z{x6dbGUeSjX;$6?nGfD)!R{J;BA)w~-UJrRFOr8~S3I4J>!#6I%t@dTQ8D9eDM{9(
z<fK$nPM%{*mcvrwDqFZ@;i{rkQ@q0cBf1+pDAL{F<@S}dzw}8__aQd53lp$0lt!3&
zfCF9>my5dh6zu)l{0xgqrUs%F;s7pzcuiCyw7m-g491=hsD*`(r<Vi>!rFhE7c*A|
z^$0KoYkx8aGM<4iWi4gHFn28p#PnHYCEJ!mm&zs$1Yo}o_8<4BdqCPgZH1^ih#_l*
zbXJi?1BiYozc-RSx`iGCtSUENWqTi{MF69)bguDc+dL`=5R9cx<3BJs&X~$V^Jy;u
z3o9)&z6TgQ-VlV1!KU20r;W*MX))aaB*e}_+Ktr$4tUqFM57AD(#6J3wB95l>t0O1
zkfEF%DWf@pegyv-!5qVg0T^9LZx9%b?t!LoZ106Kd}A%mL)R54iUn2BuL(qA$0t%Z
zJ6}azvSF2|`zkGQKf#`zBps^)4MUlEIZXm~;aOS$VpP-Em6)-azNruAZ;ZjF6?Bf~
zWU~O#7{Uy*nezbM3wV8#$&aZo(eHTYoHB?S?pU<7nu5^!x}gNC577&(a0hK55W{*;
znSueWSB%3o*Y>gAT{M(HELskjqFG!$JumYf>-fbK#H{tSlHh=B6J;$ebRK{Wn>L%~
zYH#inARfE-8aFX+d$|A!IH8!vVNJb3#7o7-Pnq9Q`kV}_aqkKGxR`i&?o*7Oq~8;L
z97h|6@C}K=_JPVW)_9uE7a$3HrU-Gk)d_mM^fwaB9%`qD1W0CnE#_!oaqrOc1X8f4
z3*yjvkPnTTi)0q7?xf3QNX4#okjPTH>3af<N7o`=T=bu0H3mN+e8HA~Osff`VXfX6
z#D;%DuL>mH;+ZlkhQ)tQdj#`@Bzub8p2#PS6>ATwWANa1SX4Jqs%H~=>DvS{n0SRQ
zF-jGp?x*}j^zT(C;;k*hbUeIPxLJ3N-qPR0J(`4$&&}NZYVJwRcsRrce@nk1a4%jS
zL@ii(+1$mh{Xhc*xDOrwrEg+YnpBLgUuZJR|B1dpU@|s&c=KL<%{)Wfp2yz3Ne|1W
zHKOj~qQqN#Y4u@aM?{5}+eH3gCgva0#~g1Bm<8<e2_*>H(&hP}<$W6F{~aD<C3dA&
zkPF78@U7{X|Cu-voo&hy*6pVx2r$FblO2Y!Em9cE8m}A|<Z<!i_`xjn{{afwV?&hZ
z1-Ku34T7B|k5IY<$VSVXG@XwONnzO*<y8T4F!wFlf;nGF&8#zAS#N+!mKCEMBl@Y_
z(gPlMz$2`{sx%2O6Ww+>6D=EPsD`y&fLW~LBWVJ#41eVe(V!pnIKoEX=4lh)A^i5N
z^b}q<DpRrkoVtrShbsFB%=Tvbvk%k5-b^!;bXjCNV0>g82IIMrZk=A|-kHWaDwI@W
zEacDTahZqy4;igqkz|eW%6x!Fe5fBqPW>sn=u}1v;OtMF??b#$BQEeJp6^ZU(ufPa
ziOZDl4FK$Pg))ig=W@0M$K3(z|449tUxFXQ(iZh?*059U1Xi;_Sq88W9c{`7$a7oG
zoX={{KHeX1(VYXj*c)$&Pe7M?<JBv?+XR;0tdxVv#p6l($FrDADcUNPuH#h!PyYs9
zmoD$nxSzm|p~?ZwX(ho}GfX-As|UzEXx2V2!;W$~9jlU*D$Hn8KGZ6;pszT}(62$g
zjxjA#xaQ2&zRl$r5~PISm@f6NXw6U%8+S`Z?8Zrj5_l5*Wj;;1zvDltIr~XCa`)cH
z)~OKBoM$wzS72=qlxaRb4D6#0#YUhUbBX*UHbyCnk(cvK+<Hw4U>Om-pxZhXL4;Lz
zsgtLC>ST5Q>aOUYj5T*oMx}Q$s%|I4z@}YMP72`mPKKYFWY(|b#@FA4>uDdZ4gI+`
z_UC%$&RoxWb8Ye|lFi;+S9uMy*B$D;M8A$dQGFM>tv+-${po7^(`~ymoyVJQyARzC
zZ#t(Iwdc6;op<5d<-@hRKiBj9x$5uCwa1%luTSSU_;kMfTjwKx<b}J=_kF(ez1e5J
zzj){Q-r_yq_j~gl@QK?&Z@y>L>juf7wY%fjb~hI$*}1_cE{E8+qh&K6MJJR68s?@x
z%)<y9s6)dHC2YZNwI1LV>}`;O>wcE*$4h6`6b%)Doq9*L@qaD<gLG_dP#+ME*rG6G
zw-n4qb*i5UnyFTF?~@`iCqtRZDx1~y0vyHM)5=BmS+^S8cj6e!ZC926TlBHIwJ%4<
zZ^K8j>8<KSBN$orNwt*dU*=!iJhs5|x5Ii6`qGWJhAES^y9`6}jRC*S*UKGh7=aV)
zsGri-$C^ptB=#(lNB$aE?6%1U%<z}PwX3JF$*7behdjd)-&a2%@H&efp?oB0(H*0m
zIL%^R%FDoxe5}qSa0dM&_`luXG0y-a7gSM}Ogz%hM<9>%9%enIo&&5bryI5Vul*lO
Chn@2P

delta 3122
zc-nQAdsJ0r7QpZR&b{Z{$M+q<AW8>$h#D$zQBW8a!OXV_g`-ni7r{s215$h&T*c8$
z5xmMaM1^EjN)x5nW?3@Jnao$<&`iD(8fPtC)<iX~YL+w3chF_Gd-1Hb_aEP5@85oW
zd!3^8Aw{Q#ly(n{Hkp+7O}~6y%K8tqM4MurNr!W)G;21qnT!)2ZvBfVkZ<$MeyV1&
za>#9!i+^-$Qtxo9QkS_cQm=EHrC#M$q<-1Wq;|QD>%S|MYQn2hjaVhs(3Mift&pnc
zGO2njkt%47%f8NK2PsU7BE>AlB1M&=NwG??Niohj$Ytj>F_<4}3C8v>903$PfnQP}
z5Szc^;S`n5uPM+K%Wga7QeGzaDDViD{p<+F^JzSvHcaJ<wet0vswSJ1Es$Iv$YVg=
zI&QJqRErU-l@z-55)Wcp@V@*4v*|OeKA{Z9sz~0;2)m1vM=@hH3&xbmY#D8F@%fq&
z_ha;86+Z%4wA6NkcFpHA0UpQvX|_8J`CL(;8|J%g|G=;~+YpK@;B5@LQ+|%^G+@|J
zYY0|_*)z)5+LCDga=s1NZxSftgsnuuE}vNE8P-EFf3EEmI`1$uH5KtMHCRH2*7J15
z5+ZlQDXkl`0`X1!M+On-?rM+16K${vKPu<XVBU2#nnKF>*9;=D@e8$yTDI~$&AQBN
zx-~3uAH(MDECq{#t&fxAH9i>V(oQ}D%u&_-mtyK}{;?%Y`sjt#uk+`PAZrxpjS*y>
zO0Ez2F2ME;_5jj9;@<<-9kZGZ+&&mzXAeQ=2i65xa)Mu?oLat{!4uSW%pL~lyl(4m
zgtmv;4)RC_(HOqp-jCwyc#8)8u<^h45OUV>LWW%?**Wb!#-{`HmjL!@hR;0;#9-4d
z+Xj-h3lxaO;mdg(mR4HLcx{&LA_e@JZ_;1|?mEj~HaibaTTc8O|AAThO0;-{Z&);*
z=q(mfRTIxvU;s9cR^o883oLl;?<|a_wD1E845Wa)j($LK7kLYV1Z+M7ap<fC6-%$O
z$y9QM7icgD&#Zw&O1{odD=--Iav=oyKiNtQdqw$@3U2Ze21!_Ev4v3gulWsyC5L-P
z_lThZ?YvoW{C03caza94wlm&|WykftSi2Q+%e$(TH2gL{$zTYXf8z6O>PoZe=d45w
zyseMGyBn49cyP6Hr(6+tEr~Ls6imC~kl~j|fYPCGfF8AoZx{^6)<<|a7PdOh(6?3*
zq(CaBbrBz9(J*xu<^_r*$`ayD25DIBv2?@M_Z$<9<>~ZEfH<hxSD8&$a})2%&*+bM
zI`o*3?KVt09En*+EHU+UL6d=6&x#OeNYS#vsQXix^%cya1!F{+qRkkTESE-M)@5@j
zx=xEj)D$HKDlpp9JgFzf?p1rz#B@=wXoCg}k_X3N;J+b<=JXdk6c~$bRwaRwoZ^fE
z<1qZMJO$GSs)8mZh<6njj~Rc`!ZH1pT0^IjM6nfKrHN_c2(vsXEj{gV2faWuMv7_$
zCZRh)8;ju;Jkr40sz5q5UQmYvrS=lXnE{>QN$c7B0Z)Sh&)|2Tsw=QPRE)vOR{aff
z#fUu&p7mzR^kbUr&Eyg(8mXnC9<<Oxi^;ux7&VrOA<UK|9Zr-o6$7W(oL)Jks!<{v
z;P-yK&!ObKNLLq$-U>YL%R0@Eb(O(7-JA6VZ`NXi^+j*i_2LIBnCQbY@g%cMk!&;S
z-9g2_ls2oQwAq+{Og~Ax59p_WN-M-dfE-LaEzYB?Y6-b^8g6I$;?3$jm9xF^=J=)Z
zC2zbsA>SFJl%rxP*mKW@y1_S}SyJX=yhog=FA7?FAG|z8+h%aj!^Rk~AJgkt7?#G0
zPwz#5GJ+aodp<U9<m0huyePud)8aFuM`v`j#R3ed*V{2>uNq|pbE9K14<q`C2<&@J
z{~J0p1!7f&I+K1pCpd$A4AkTtY5E@Qn7)rip$zXF){TJy<Z3peeg(^#VUZEzb3hk9
z7x4@hVg}O|W7RM*7iA-7;^uGFAWBV^t=w=$C}t>lNS`eB>ystEeZADT7|S{@#&Yjs
ztawliD~<a}ysyAY?_%6BdPTY4D~qI)!iVq``SH1Z`BwY#t?8Vv*qd*yU$gw-*L;H=
z7UNgrwTEzR@Z);jmusUh*QU<7O1!x?`*D@}zA^eBMjy#6>!l0NL+G~p(QWgkEBB?t
z&gr&$)4kz00V=%dCg?J2Tcq)w51s70{3rWvzsX+J`DCy5p6qXWbM5iVT8%eXrQU8;
zHRHLb-FxnioWTjwV5O9O^j&YwAxF_!G26i0(1E!hp@OFwn30TTzoS<I)MDFiHLUzU
z>eG1bs-A41BG9pmdc6E!`5&ZUUA_LS@>YB_MpUR_)Z>bNSusq#jqW{aA56~_nN)aG
zFIM0HW;BVbbosg-)^Xw>WweNSK)E;d%^kIQ=K*{l8h=tBVFN3boYV7}Wv|>l?1>L<
zd63px=qNMZjTNJeyGJl0%NBHhzP5g@_he8{hoeM82kTe{?_zVV7J4tS*c7i>F*Q(&
zGOoUd)uCb$O334s*ruOn&_J<HaX~S%+t)Zj6k9Cb20C<8&tz~E1A8gm9$+2^V*k?3
bnrf4o-q8zXrgxI_ynYt2a3f!5+^_pToWBva

-- 
2.47.2