/ Check-in [07788c0f]
Login

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

Overview
Comment:Allocate the correct size for the output buffer in fts3DoclistOrMerge(). Fix for [56be976859].
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: 07788c0f7f3740c1c280f6ce4dc68401c30bae6e
User & Date: dan 2011-09-13 19:08:43
References
2011-09-14
11:16 Closed ticket [56be9768]: Buffer overrun in FTS prefix queries plus 2 other changes artifact: e4256312 user: dan
Context
2011-09-14
13:23
Remove code from vdbesort.c that was made unreachable by the recent sqlite3VdbeRecordUnpack() optimizations. check-in: 607aba6c user: drh tags: trunk
2011-09-13
19:08
Allocate the correct size for the output buffer in fts3DoclistOrMerge(). Fix for [56be976859]. check-in: 07788c0f user: dan tags: trunk
2011-09-11
10:14
Cleanup pdb/ilk files generated by the MSVC makefile. check-in: a9db247b user: mistachkin tags: trunk
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to ext/fts3/fts3.c.

  2062   2062     char *p2 = a2;
  2063   2063     char *p;
  2064   2064     char *aOut;
  2065   2065     int bFirstOut = 0;
  2066   2066   
  2067   2067     *paOut = 0;
  2068   2068     *pnOut = 0;
  2069         -  aOut = sqlite3_malloc(n1+n2);
         2069  +
         2070  +  /* Allocate space for the output. Both the input and output doclists
         2071  +  ** are delta encoded. If they are in ascending order (bDescDoclist==0),
         2072  +  ** then the first docid in each list is simply encoded as a varint. For
         2073  +  ** each subsequent docid, the varint stored is the difference between the
         2074  +  ** current and previous docid (a positive number - since the list is in
         2075  +  ** ascending order).
         2076  +  **
         2077  +  ** The first docid written to the output is therefore encoded using the 
         2078  +  ** same number of bytes as it is in whichever of the input lists it is
         2079  +  ** read from. And each subsequent docid read from the same input list 
         2080  +  ** consumes either the same or less bytes as it did in the input (since
         2081  +  ** the difference between it and the previous value in the output must
         2082  +  ** be a positive value less than or equal to the delta value read from 
         2083  +  ** the input list). The same argument applies to all but the first docid
         2084  +  ** read from the 'other' list. And to the contents of all position lists
         2085  +  ** that will be copied and merged from the input to the output.
         2086  +  **
         2087  +  ** However, if the first docid copied to the output is a negative number,
         2088  +  ** then the encoding of the first docid from the 'other' input list may
         2089  +  ** be larger in the output than it was in the input (since the delta value
         2090  +  ** may be a larger positive integer than the actual docid).
         2091  +  **
         2092  +  ** The space required to store the output is therefore the sum of the
         2093  +  ** sizes of the two inputs, plus enough space for exactly one of the input
         2094  +  ** docids to grow. 
         2095  +  **
         2096  +  ** A symetric argument may be made if the doclists are in descending 
         2097  +  ** order.
         2098  +  */
         2099  +  aOut = sqlite3_malloc(n1+n2+FTS3_VARINT_MAX-1);
  2070   2100     if( !aOut ) return SQLITE_NOMEM;
  2071   2101   
  2072   2102     p = aOut;
  2073   2103     fts3GetDeltaVarint3(&p1, pEnd1, 0, &i1);
  2074   2104     fts3GetDeltaVarint3(&p2, pEnd2, 0, &i2);
  2075   2105     while( p1 || p2 ){
  2076   2106       sqlite3_int64 iDiff = DOCID_CMP(i1, i2);
................................................................................
  2089   2119         fts3PoslistCopy(&p, &p2);
  2090   2120         fts3GetDeltaVarint3(&p2, pEnd2, bDescDoclist, &i2);
  2091   2121       }
  2092   2122     }
  2093   2123   
  2094   2124     *paOut = aOut;
  2095   2125     *pnOut = (p-aOut);
         2126  +  assert( *pnOut<=n1+n2+FTS3_VARINT_MAX-1 );
  2096   2127     return SQLITE_OK;
  2097   2128   }
  2098   2129   
  2099   2130   /*
  2100   2131   ** This function does a "phrase" merge of two doclists. In a phrase merge,
  2101   2132   ** the output contains a copy of each position from the right-hand input
  2102   2133   ** doclist for which there is a position in the left-hand input doclist

Changes to test/fts3sort.test.

   153    153       INSERT INTO t2 VALUES('cc aa');
   154    154       SELECT docid FROM t2 WHERE t2 MATCH 'aa';
   155    155     END;
   156    156   } {3 1}
   157    157   do_execsql_test 2.3 {
   158    158     SELECT docid FROM t2 WHERE t2 MATCH 'aa';
   159    159   } {3 1}
          160  +
          161  +#-------------------------------------------------------------------------
          162  +# Test that ticket [56be976859] has been fixed.
          163  +#
          164  +do_execsql_test 3.1 {
          165  +  CREATE VIRTUAL TABLE t3 USING fts4(x, order=DESC);
          166  +  INSERT INTO t3(docid, x) VALUES(113382409004785664, 'aa');
          167  +  INSERT INTO t3(docid, x) VALUES(1, 'ab');
          168  +  SELECT rowid FROM t3 WHERE x MATCH 'a*' ORDER BY docid DESC;
          169  +} {113382409004785664 1}
          170  +do_execsql_test 3.2 {
          171  +  CREATE VIRTUAL TABLE t4 USING fts4(x);
          172  +  INSERT INTO t4(docid, x) VALUES(-113382409004785664, 'aa');
          173  +  INSERT INTO t4(docid, x) VALUES(1, 'ab');
          174  +  SELECT rowid FROM t4 WHERE x MATCH 'a*';
          175  +} {-113382409004785664 1}
          176  +
          177  +
   160    178   
   161    179   finish_test
   162    180