hstore_compat.c

   1 /*
   2  * contrib/hstore/hstore_compat.c
   3
   4 Current nested hstore layout (see historical notes below):
   5
   6 Hstore consists of varlena header, 4 bits (special flags), 28 bits for
   7 nelems/npairs, array of hentries and element array. Special flags are
   8 HS_FLAG_NEWVERSION,  HS_FLAG_ARRAY, HS_FLAG_HASH, HS_FLAG_SCALAR. Hentry
   9 starts from 4 special bits: 1st bit (ISFIRST) is set if there is no previous
  10 entry, next 3 bits are used to indicate type of hstore value (ISSTRING,
  11 ISNUMERIC, ISNEST, ISNULL, ISBOOL). Other 28 bits are ending position of
  12 hentry value relative to the beginning of element array.
  13
  14 Hash key-value accessed as follow:
  15 first key starts from zero and ends at Hentry[0],i-th key starts from
  16 Hentry[i*2-1] and ends at Hentry[i*2], i-th value starts from
  17 align(HEntry[i*2]) and ends at HEntry[i*2 + 1]. Key-Value pairs are
  18 lexicographically ordered by keys.
  19
  20 Array's first element starts from zero and ends at Hentry[0], and
  21 i-th element starts from align(HEntry[i - 1]) and ends at HEntry[i]. Elements
  22 are not ordered.
  23
  24 Notes:
  25 Scalar stored as a single-element array.
  26
  27 Limitations:
  28 Number of elements in array: 2^28
  29 Number of pairs in hash: 2^28
  30 Length of string: 2^28 bytes
  31 Length of nested hash or array: 2^28 bytes
  32
  33  *
  34  * Notes on old/new hstore format disambiguation.
  35  *
  36  * There are three formats to consider:
  37  * 1) old contrib/hstore (referred to as hstore-old)
  38  * 2) prerelease pgfoundry hstore
  39  * 3) new contrib/hstore (v2)
  40  * 4) nested contrib/hstore (v3)
  41  *
  42  * (3) and (4) are upward binary compatible.
  43  * (2) and (3) are identical except for the HS_FLAG_NEWVERSION
  44  * bit, which is set in (3) but not (2).
  45  *
  46  * Values that are already in format (3), or which are
  47  * unambiguously in format (2), are handled by the first
  48  * "return immediately" test in hstoreUpgrade().
  49  *
  50  * To stress a point: we ONLY get here with possibly-ambiguous
  51  * values if we're doing some sort of in-place migration from an
  52  * old prerelease pgfoundry hstore-new; and we explicitly don't
  53  * support that without fixing up any potentially padded values
  54  * first. Most of the code here is serious overkill, but the
  55  * performance penalty isn't serious (especially compared to the
  56  * palloc() that we have to do anyway) and the belt-and-braces
  57  * validity checks provide some reassurance. (If for some reason
  58  * we get a value that would have worked on the old code, but
  59  * which would be botched by the conversion code, the validity
  60  * checks will fail it first so we get an error rather than bad
  61  * data.)
  62  *
  63  * Note also that empty hstores are the same in (2) and (3), so
  64  * there are some special-case paths for them.
  65  *
  66  * We tell the difference between formats (2) and (3) as follows (but
  67  * note that there are some edge cases where we can't tell; see
  68  * comments in hstoreUpgrade):
  69  *
  70  * First, since there must be at least one entry, we look at
  71  * how the bits line up. The new format looks like:
  72  *
  73  * 10kkkkkkkkkkkkkkkkkkkkkkkkkkkkkk  (k..k = keylen)
  74  * 0nvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv  (v..v = keylen+vallen)
  75  *
  76  * The old format looks like one of these, depending on endianness
  77  * and bitfield layout: (k..k = keylen, v..v = vallen, p..p = pos,
  78  * n = isnull)
  79  *
  80  * kkkkkkkkkkkkkkkkvvvvvvvvvvvvvvvv
  81  * nppppppppppppppppppppppppppppppp
  82  *
  83  * kkkkkkkkkkkkkkkkvvvvvvvvvvvvvvvv
  84  * pppppppppppppppppppppppppppppppn
  85  *
  86  * vvvvvvvvvvvvvvvvkkkkkkkkkkkkkkkk
  87  * nppppppppppppppppppppppppppppppp
  88  *
  89  * vvvvvvvvvvvvvvvvkkkkkkkkkkkkkkkk
  90  * pppppppppppppppppppppppppppppppn   (usual i386 format)
  91  *
  92  * If the entry is in old format, for the first entry "pos" must be 0.
  93  * We can obviously see that either keylen or vallen must be >32768
  94  * for there to be any ambiguity (which is why lengths less than that
  95  * are fasttracked in hstore.h) Since "pos"==0, the "v" field in the
  96  * new-format interpretation can only be 0 or 1, which constrains all
  97  * but three bits of the old-format's k and v fields. But in addition
  98  * to all of this, the data length implied by the keylen and vallen
  99  * must fit in the varlena size. So the only ambiguous edge case for
 100  * hstores with only one entry occurs between a new-format entry with
 101  * an excess (~32k) of padding, and an old-format entry. But we know
 102  * which format to use in that case based on how we were compiled, so
 103  * no actual data corruption can occur.
 104  *
 105  * If there is more than one entry, the requirement that keys do not
 106  * decrease in length, and that positions increase contiguously, and
 107  * that the end of the data not be beyond the end of the varlena
 108  * itself, disambiguates in almost all other cases. There is a small
 109  * set of ambiguous cases which could occur if the old-format value
 110  * has a large excess of padding and just the right pattern of key
 111  * sizes, but these are also handled based on how we were compiled.
 112  *
 113  * The otherwise undocumented function hstore_version_diag is provided
 114  * for testing purposes.
 115  */
 116 #include "postgres.h"
 117
 118
 119 #include "hstore.h"
 120
 121 /*
 122  * This is the structure used for entries in the old contrib/hstore
 123  * implementation. Notice that this is the same size as the new entry
 124  * (two 32-bit words per key/value pair) and that the header is the
 125  * same, so the old and new versions of ARRPTR, STRPTR, CALCDATASIZE
 126  * etc. are compatible.
 127  *
 128  * If the above statement isn't true on some bizarre platform, we're
 129  * a bit hosed (see StaticAssertStmt in hstoreValidOldFormat).
 130  */
 131 typedef struct
 132 {
 133         uint16          keylen;
 134         uint16          vallen;
 135         uint32
 136                                 valisnull:1,
 137                                 pos:31;
 138 } HOldEntry;
 139
 140 /*
 141  * New Old version (new not-nested version of hstore, v2 version)
 142  * V2 and v3 (nested) are upward binary compatible. But
 143  * framework was fully changed. Keep here old definitions (v2)
 144  */
 145
 146
 147 typedef struct
 148 {
 149         int32       vl_len_;        /* varlena header (do not touch directly!) */
 150         uint32      size_;          /* flags and number of items in hstore */
 151         /* array of HEntry follows */
 152 } HStoreV2;
 153
 154 static int      hstoreValidNewFormat(HStoreV2 *hs);
 155 static int      hstoreValidOldFormat(HStoreV2 *hs);
 156
 157 #define HS_COUNT(hsp_)     (HS_ISEMPTY(hsp_) ? 0 : ((hsp_)->size_ & HS_COUNT_MASK))
 158 #define HS_SETCOUNT(hsp_,c_)    ((hsp_)->size_ = (c_) | HS_FLAG_NEWVERSION | ((hsp_)->size_ & ~HS_COUNT_MASK))
 159
 160 /*
 161  * "x" comes from an existing HS_COUNT() (as discussed, <= INT_MAX/24) or a
 162  * Pairs array length (due to MaxAllocSize, <= INT_MAX/40).  "lenstr" is no
 163  * more than INT_MAX, that extreme case arising in hstore_from_arrays().
 164  * Therefore, this calculation is limited to about INT_MAX / 5 + INT_MAX.
 165  */
 166 #define HSHRDSIZE   (sizeof(HStoreV2))
 167 #define CALCDATASIZE(x, lenstr) ( (x) * 2 * sizeof(HEntry) + HSHRDSIZE + (lenstr) )
 168 /* note multiple evaluations of x */
 169 #define ARRPTR(x)       ( (HEntry*) ( (HStoreV2*)(x) + 1 ) )
 170 #define STRPTR(x)       ( (char*)(ARRPTR(x) + HS_ROOT_COUNT((HStoreV2*)(x)) * 2) )
 171
 172 /* note multiple/non evaluations */
 173 #define HS_KEYLEN(arr_,i_) (HSE_LEN((arr_)[2*(i_)]))
 174
 175 /* ensure the varlena size of an existing hstore is correct */
 176 #define HS_FIXSIZE(hsp_,count_)                                         \
 177         do {                                                                \
 178                 int bl = (count_) ? HSE_ENDPOS(ARRPTR(hsp_)[2*(count_)-1]) : 0; \
 179                 SET_VARSIZE((hsp_), CALCDATASIZE((count_),bl));                 \
 180         } while (0)
 181
 182 /*
 183  * Validity test for a new-format hstore.
 184  *      0 = not valid
 185  *      1 = valid but with "slop" in the length
 186  *      2 = exactly valid
 187  */
 188 static int
 189 hstoreValidNewFormat(HStoreV2 *hs)
 190 {
 191         int                     count = HS_COUNT(hs);
 192         HEntry     *entries = ARRPTR(hs);
 193         int                     buflen = (count) ? HSE_ENDPOS(entries[2 * (count) - 1]) : 0;
 194         int                     vsize = CALCDATASIZE(count, buflen);
 195         int                     i;
 196
 197         if (hs->size_ & HS_FLAG_NEWVERSION)
 198                 return 2;
 199
 200         if (count == 0)
 201                 return 2;
 202
 203         if (!HSE_ISFIRST(entries[0]))
 204                 return 0;
 205
 206         if (vsize > VARSIZE(hs))
 207                 return 0;
 208
 209         /* entry position must be nondecreasing */
 210
 211         for (i = 1; i < 2 * count; ++i)
 212         {
 213                 if (HSE_ISFIRST(entries[i])
 214                         || (HSE_ENDPOS(entries[i]) < HSE_ENDPOS(entries[i - 1])))
 215                         return 0;
 216         }
 217
 218         /* key length must be nondecreasing and keys must not be null */
 219
 220         for (i = 1; i < count; ++i)
 221         {
 222                 if (HS_KEYLEN(entries, i) < HS_KEYLEN(entries, i - 1))
 223                         return 0;
 224                 if (HSE_ISNULL(entries[2 * i]))
 225                         return 0;
 226         }
 227
 228         if (vsize != VARSIZE(hs))
 229                 return 1;
 230
 231         return 2;
 232 }
 233
 234 /*
 235  * Validity test for an old-format hstore.
 236  *      0 = not valid
 237  *      1 = valid but with "slop" in the length
 238  *      2 = exactly valid
 239  */
 240 static int
 241 hstoreValidOldFormat(HStoreV2 *hs)
 242 {
 243         int                     count = hs->size_;
 244         HOldEntry  *entries = (HOldEntry *) ARRPTR(hs);
 245         int                     vsize;
 246         int                     lastpos = 0;
 247         int                     i;
 248
 249         if (hs->size_ & HS_FLAG_NEWVERSION)
 250                 return 0;
 251
 252         /* New format uses an HEntry for key and another for value */
 253         StaticAssertStmt(sizeof(HOldEntry) == 2 * sizeof(HEntry),
 254                                          "old hstore format is not upward-compatible");
 255
 256         if (count == 0)
 257                 return 2;
 258
 259         if (count > 0xFFFFFFF)
 260                 return 0;
 261
 262         if (CALCDATASIZE(count, 0) > VARSIZE(hs))
 263                 return 0;
 264
 265         if (entries[0].pos != 0)
 266                 return 0;
 267
 268         /* key length must be nondecreasing */
 269
 270         for (i = 1; i < count; ++i)
 271         {
 272                 if (entries[i].keylen < entries[i - 1].keylen)
 273                         return 0;
 274         }
 275
 276         /*
 277          * entry position must be strictly increasing, except for the first entry
 278          * (which can be ""=>"" and thus zero-length); and all entries must be
 279          * properly contiguous
 280          */
 281
 282         for (i = 0; i < count; ++i)
 283         {
 284                 if (entries[i].pos != lastpos)
 285                         return 0;
 286                 lastpos += (entries[i].keylen
 287                                         + ((entries[i].valisnull) ? 0 : entries[i].vallen));
 288         }
 289
 290         vsize = CALCDATASIZE(count, lastpos);
 291
 292         if (vsize > VARSIZE(hs))
 293                 return 0;
 294
 295         if (vsize != VARSIZE(hs))
 296                 return 1;
 297
 298         return 2;
 299 }
 300
 301
 302 /*
 303  * hstoreUpgrade: PG_DETOAST_DATUM plus support for conversion of old hstores
 304  */
 305 HStore *
 306 hstoreUpgrade(Datum orig)
 307 {
 308         HStoreV2           *hs = (HStoreV2 *) PG_DETOAST_DATUM(orig);
 309         int                     valid_new;
 310         int                     valid_old;
 311         bool            writable;
 312
 313         /* Return immediately if no conversion needed */
 314         if (VARSIZE_ANY(hs) <= VARHDRSZ ||
 315                 (hs->size_ & HS_FLAG_NEWVERSION) ||
 316                 hs->size_ == 0 ||
 317                 (VARSIZE(hs) < 32768 && HSE_ISFIRST((ARRPTR(hs)[0]))))
 318         {
 319                 if (VARSIZE_ANY_EXHDR(hs) == sizeof(hs->size_))
 320                 {
 321                         /* 'new' format but not nested. And empty */
 322                         hs = palloc(sizeof(VARHDRSZ));
 323                         SET_VARSIZE(hs, VARHDRSZ);
 324                 }
 325
 326                 return (HStore*)hs;
 327         }
 328
 329         valid_new = hstoreValidNewFormat(hs);
 330         valid_old = hstoreValidOldFormat(hs);
 331         /* Do we have a writable copy? */
 332         writable = ((void *) hs != (void *) DatumGetPointer(orig));
 333
 334         if (!valid_old || hs->size_ == 0)
 335         {
 336                 if (valid_new)
 337                 {
 338                         /*
 339                          * force the "new version" flag and the correct varlena length,
 340                          * but only if we have a writable copy already (which we almost
 341                          * always will, since short new-format values won't come through
 342                          * here)
 343                          */
 344                         if (writable)
 345                         {
 346                                 HS_SETCOUNT(hs, HS_COUNT(hs));
 347                                 HS_FIXSIZE(hs, HS_COUNT(hs));
 348                         }
 349                         return (HStore*)hs;
 350                 }
 351                 else
 352                 {
 353                         elog(ERROR, "invalid hstore value found");
 354                 }
 355         }
 356
 357         /*
 358          * this is the tricky edge case. It is only possible in some quite extreme
 359          * cases (the hstore must have had a lot of wasted padding space at the
 360          * end). But the only way a "new" hstore value could get here is if we're
 361          * upgrading in place from a pre-release version of hstore-new (NOT
 362          * contrib/hstore), so we work off the following assumptions: 1. If you're
 363          * moving from old contrib/hstore to hstore-new, you're required to fix up
 364          * any potential conflicts first, e.g. by running ALTER TABLE ... USING
 365          * col::text::hstore; on all hstore columns before upgrading. 2. If you're
 366          * moving from old contrib/hstore to new contrib/hstore, then "new" values
 367          * are impossible here 3. If you're moving from pre-release hstore-new to
 368          * hstore-new, then "old" values are impossible here 4. If you're moving
 369          * from pre-release hstore-new to new contrib/hstore, you're not doing so
 370          * as an in-place upgrade, so there is no issue So the upshot of all this
 371          * is that we can treat all the edge cases as "new" if we're being built
 372          * as hstore-new, and "old" if we're being built as contrib/hstore.
 373          *
 374          * XXX the WARNING can probably be downgraded to DEBUG1 once this has been
 375          * beta-tested. But for now, it would be very useful to know if anyone can
 376          * actually reach this case in a non-contrived setting.
 377          */
 378
 379         if (valid_new)
 380         {
 381 #if HSTORE_IS_HSTORE_NEW
 382                 elog(WARNING, "ambiguous hstore value resolved as hstore-new");
 383
 384                 /*
 385                  * force the "new version" flag and the correct varlena length, but
 386                  * only if we have a writable copy already (which we almost always
 387                  * will, since short new-format values won't come through here)
 388                  */
 389                 if (writable)
 390                 {
 391                         HS_SETCOUNT(hs, HS_COUNT(hs));
 392                         HS_FIXSIZE(hs, HS_COUNT(hs));
 393                 }
 394                 return hs;
 395 #else
 396                 elog(WARNING, "ambiguous hstore value resolved as hstore-old");
 397 #endif
 398         }
 399
 400         /*
 401          * must have an old-style value. Overwrite it in place as a new-style one,
 402          * making sure we have a writable copy first.
 403          */
 404
 405         if (!writable)
 406                 hs = (HStoreV2 *) PG_DETOAST_DATUM_COPY(orig);
 407
 408         {
 409                 int                     count = hs->size_;
 410                 HEntry     *new_entries = ARRPTR(hs);
 411                 HOldEntry  *old_entries = (HOldEntry *) ARRPTR(hs);
 412                 int                     i;
 413
 414                 for (i = 0; i < count; ++i)
 415                 {
 416                         uint32          pos = old_entries[i].pos;
 417                         uint32          keylen = old_entries[i].keylen;
 418                         uint32          vallen = old_entries[i].vallen;
 419                         bool            isnull = old_entries[i].valisnull;
 420
 421                         if (isnull)
 422                                 vallen = 0;
 423
 424                         new_entries[2 * i].entry = (pos + keylen) & HENTRY_POSMASK;
 425                         new_entries[2 * i + 1].entry = (((pos + keylen + vallen) & HENTRY_POSMASK)
 426                                                                                         | ((isnull) ? HENTRY_ISNULL : 0));
 427                 }
 428
 429                 if (count)
 430                         new_entries[0].entry |= HENTRY_ISFIRST;
 431                 HS_SETCOUNT(hs, count);
 432                 HS_FIXSIZE(hs, count);
 433         }
 434
 435         return (HStore*)hs;
 436 }
 437
 438
 439 PG_FUNCTION_INFO_V1(hstore_version_diag);
 440 Datum           hstore_version_diag(PG_FUNCTION_ARGS);
 441 Datum
 442 hstore_version_diag(PG_FUNCTION_ARGS)
 443 {
 444         HStoreV2           *hs = (HStoreV2 *) PG_DETOAST_DATUM(PG_GETARG_DATUM(0));
 445         int                     valid_new = hstoreValidNewFormat(hs);
 446         int                     valid_old = hstoreValidOldFormat(hs);
 447
 448         PG_RETURN_INT32(valid_old * 10 + valid_new);
 449 }