OSX/libsecurity_filedb/lib/DbIndex.cpp

   1 /*
   2  * Copyright (c) 2000-2001,2011-2012,2014 Apple Inc. All Rights Reserved.
   3  *
   4  * The contents of this file constitute Original Code as defined in and are
   5  * subject to the Apple Public Source License Version 1.2 (the 'License').
   6  * You may not use this file except in compliance with the License. Please obtain
   7  * a copy of the License at http://www.apple.com/publicsource and read it before
   8  * using this file.
   9  *
  10  * This Original Code and all software distributed under the License are
  11  * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER EXPRESS
  12  * OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES, INCLUDING WITHOUT
  13  * LIMITATION, ANY WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR
  14  * PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT. Please see the License for the
  15  * specific language governing rights and limitations under the License.
  16  */
  17
  18
  19 //
  20 // DbIndex.cpp
  21 //
  22
  23 #include "DbIndex.h"
  24 #include "AppleDatabase.h"
  25 #include <stdio.h>
  26
  27 DbQueryKey::DbQueryKey(const DbConstIndex &index)
  28 :       mIndex(index),
  29         mTableSection(index.table().getTableSection())
  30 {
  31 }
  32
  33 // Perform a less-than comparison between two keys. An offset of
  34 // kUseQueryKeyOffset means to use the key provided as part of the
  35 // query; otherwise, the key comes from the database.
  36
  37 const uint32 DbKeyComparator::kUseQueryKeyOffset;
  38
  39 bool
  40 DbKeyComparator::operator () (uint32 offset1, uint32 offset2) const
  41 {
  42         ReadSection rs1, rs2;
  43         const ReadSection *key1, *key2;
  44
  45         // get the read sections to compare
  46
  47         if (offset1 == kUseQueryKeyOffset)
  48                 key1 = &mKey.mKeyData;
  49         else {
  50                 rs1 = mKey.mTableSection.subsection(offset1);
  51                 key1 = &rs1;
  52         }
  53
  54         if (offset2 == kUseQueryKeyOffset)
  55                 key2 = &mKey.mKeyData;
  56         else {
  57                 rs2 = mKey.mTableSection.subsection(offset2);
  58                 key2 = &rs2;
  59         }
  60
  61         // compare the values of the attributes in the keys
  62
  63         uint32 valueOffset1 = sizeof(uint32), valueOffset2 = sizeof(uint32);
  64
  65         for (uint32 i = 0; i < mKey.mNumKeyValues; i++) {
  66                 const MetaAttribute &metaAttribute = *mKey.mIndex.mAttributes[i];
  67                 auto_ptr<DbValue> value1(metaAttribute.createValue(*key1, valueOffset1));
  68                 auto_ptr<DbValue> value2(metaAttribute.createValue(*key2, valueOffset2));
  69
  70                 if (metaAttribute.evaluate(value1.get(), value2.get(), CSSM_DB_LESS_THAN))
  71                         return true;
  72
  73                 else if (metaAttribute.evaluate(value2.get(), value1.get(), CSSM_DB_LESS_THAN))
  74                         return false;
  75         }
  76
  77         // if we are here, the keys are equal
  78
  79         return false;
  80 }
  81
  82 // Comparison used when inserting an item into an index, but otherwise
  83 // similar to the version above.
  84
  85 bool
  86 DbIndexKey::operator < (const DbIndexKey &other) const
  87 {
  88         // compare the values of the attributes in the keys
  89
  90         uint32 numAttributes = (uint32) mIndex.mAttributes.size();
  91         uint32 valueOffset1 = 0, valueOffset2 = 0;
  92
  93         for (uint32 i = 0; i < numAttributes; i++) {
  94                 const MetaAttribute &metaAttribute = *mIndex.mAttributes[i];
  95                 auto_ptr<DbValue> value1(metaAttribute.createValue(mKeySection.subsection(mKeyRange),
  96                         valueOffset1));
  97                 auto_ptr<DbValue> value2(metaAttribute.createValue(other.mKeySection.subsection(other.mKeyRange),
  98                         valueOffset2));
  99
 100                 if (metaAttribute.evaluate(value1.get(), value2.get(), CSSM_DB_LESS_THAN))
 101                         return true;
 102
 103                 else if (metaAttribute.evaluate(value2.get(), value1.get(), CSSM_DB_LESS_THAN))
 104                         return false;
 105         }
 106
 107         // if we are here, the keys are equal
 108
 109         return false;
 110 }
 111
 112 DbIndex::DbIndex(const MetaRecord &metaRecord, uint32 indexId, bool isUniqueIndex)
 113 :       mMetaRecord(metaRecord),
 114         mIndexId(indexId),
 115         mIsUniqueIndex(isUniqueIndex)
 116 {
 117 }
 118
 119 // Append an attribute to the vector used to form index keys.
 120
 121 void
 122 DbIndex::appendAttribute(uint32 attributeId)
 123 {
 124         CSSM_DB_ATTRIBUTE_INFO info;
 125         info.AttributeNameFormat = CSSM_DB_ATTRIBUTE_NAME_AS_INTEGER;
 126         info.Label.AttributeID = attributeId;
 127
 128         mAttributes.push_back(&(mMetaRecord.metaAttribute(info)));
 129 }
 130
 131 // Construct a new read-only index.
 132
 133 DbConstIndex::DbConstIndex(const Table &table, uint32 indexId, bool isUniqueIndex)
 134 :       DbIndex(table.getMetaRecord(), indexId, isUniqueIndex),
 135         mTable(table)
 136 {
 137 }
 138
 139 DbConstIndex::DbConstIndex(const Table &table, const ReadSection &indexSection)
 140 :       DbIndex(table.getMetaRecord(), indexSection.at(AtomSize), indexSection.at(2 * AtomSize)),
 141         mTable(table)
 142 {
 143         uint32 numAttributes = indexSection.at(3 * AtomSize);
 144
 145         for (uint32 i = 0; i < numAttributes; i++) {
 146                 uint32 attributeId = indexSection.at((4 + i) * AtomSize);
 147                 appendAttribute(attributeId);
 148         }
 149
 150         uint32 offset = (4 + numAttributes) * AtomSize;
 151         uint32 numRecords = indexSection.at(offset);
 152         offset += AtomSize;
 153         mKeyOffsetVector.overlay(numRecords,
 154                 reinterpret_cast<const Atom *>(indexSection.range(Range(offset, numRecords * AtomSize))));
 155
 156         offset += numRecords * AtomSize;
 157         mRecordNumberVector.overlay(numRecords,
 158                 reinterpret_cast<const Atom *>(indexSection.range(Range(offset, numRecords * AtomSize))));
 159 }
 160
 161 // Check to see if this index can be used to perform a given query, based on
 162 // the attributes used in the query and their order. They must be a prefix
 163 // of the index key attributes. If there is more than one attribute, all of the
 164 // operators must be EQUAL and the conjunctive must be AND; this is needed to
 165 // ensure that the results are a contiguous segment of the index. On success,
 166 // the appropriate index key is generated from the query.
 167
 168 bool
 169 DbConstIndex::matchesQuery(const CSSM_QUERY &query, DbQueryKey *&queryKey) const
 170 {
 171         uint32 numPredicates = query.NumSelectionPredicates;
 172
 173         if (numPredicates == 0 || numPredicates > mAttributes.size())
 174                 return false;
 175
 176         // determine which index attributes are used in the query
 177
 178         auto_array<uint32> attributeUsed(mAttributes.size());
 179         for (uint32 i = 0; i < mAttributes.size(); attributeUsed[i++] = ~(uint32)0);
 180
 181         for (uint32 i = 0, j; i < numPredicates; i++) {
 182                 const MetaAttribute &tableAttribute =
 183                         mMetaRecord.metaAttribute(query.SelectionPredicate[i].Attribute.Info);
 184
 185                 for (j = 0; j < mAttributes.size(); j++) {
 186                         if (tableAttribute.attributeId() == mAttributes[j]->attributeId()) {
 187                                 if (attributeUsed[j] != ~(uint32)0)
 188                                         // invalid query: attribute appears twice
 189                                         CssmError::throwMe(CSSMERR_DL_INVALID_QUERY);
 190                                 else {
 191                                         // the jth index component is the ith predicate in the query
 192                                         attributeUsed[j] = i;
 193                                         break;
 194                                 }
 195                         }
 196                 }
 197
 198                 if (j == mAttributes.size()) {
 199                         // the predicate attribute is not in the index, so return failure
 200                         return false;
 201                 }
 202         }
 203
 204         // check that the query predicates form a prefix of the index key, which means that
 205         // the first N index components are the N query predicates in some order
 206
 207         long lastIndex;
 208         for (lastIndex = mAttributes.size() - 1; (lastIndex >= 0) && (attributeUsed[lastIndex] == ~(uint32)0);
 209                 lastIndex--);
 210
 211         if (lastIndex != numPredicates - 1)
 212                 return false;
 213
 214         // if there is more than one predicate, the conjunctive must be AND and all the
 215         // operators must be EQUAL for the compound index to be useful
 216
 217         CSSM_DB_OPERATOR op;
 218
 219         if (numPredicates > 1) {
 220                 if (query.Conjunctive != CSSM_DB_AND)
 221                         return false;
 222
 223                 for (uint32 i = 0; i < numPredicates; i++)
 224                         if (query.SelectionPredicate[i].DbOperator != CSSM_DB_EQUAL)
 225                                 return false;
 226
 227                 op = CSSM_DB_EQUAL;
 228         }
 229
 230         // for a single predicate, check the operator
 231
 232         else {
 233                 op = query.SelectionPredicate[0].DbOperator;
 234                 if (op != CSSM_DB_EQUAL && op != CSSM_DB_LESS_THAN && op != CSSM_DB_GREATER_THAN)
 235                         return false;
 236         }
 237
 238         // ok, after all that, we can use this index, so generate an object used as a key
 239         // for this query on this index
 240
 241         queryKey = new DbQueryKey(*this);
 242         queryKey->mNumKeyValues = numPredicates;
 243         queryKey->mOp = op;
 244
 245         uint32 keyLength = sizeof(uint32);
 246         for (uint32 i = 0; i < numPredicates; i++)
 247                 mAttributes[i]->packValue(queryKey->mKeyData, keyLength,
 248                         *(query.SelectionPredicate[attributeUsed[i]].Attribute.Value));
 249         queryKey->mKeyData.put(0, keyLength - sizeof(uint32));
 250         queryKey->mKeyData.size(keyLength);
 251
 252         return true;
 253 }
 254
 255 // Perform a query on an index, returning the iterators that bound the
 256 // returned results.
 257
 258 void
 259 DbConstIndex::performQuery(const DbQueryKey &queryKey,
 260         DbIndexIterator &begin, DbIndexIterator &end) const
 261 {
 262         DbKeyComparator cmp(queryKey);
 263
 264         switch (queryKey.mOp) {
 265
 266         case CSSM_DB_EQUAL:
 267                 {
 268                         pair<DbIndexIterator, DbIndexIterator> result;
 269                         result = equal_range(mKeyOffsetVector.begin(), mKeyOffsetVector.end(),
 270                                 DbKeyComparator::kUseQueryKeyOffset, cmp);
 271                         begin = result.first;
 272                         end = result.second;
 273                 }
 274                 break;
 275
 276         case CSSM_DB_LESS_THAN:
 277                 begin = mKeyOffsetVector.begin();
 278                 end = lower_bound(begin, mKeyOffsetVector.end(),
 279                                 DbKeyComparator::kUseQueryKeyOffset, cmp);
 280                 break;
 281
 282         case CSSM_DB_GREATER_THAN:
 283                 end = mKeyOffsetVector.end();
 284                 begin = lower_bound(mKeyOffsetVector.begin(), end,
 285                                 DbKeyComparator::kUseQueryKeyOffset, cmp);
 286                 break;
 287
 288         default:
 289                 CssmError::throwMe(CSSMERR_DL_INTERNAL_ERROR);
 290                 break;
 291         }
 292 }
 293
 294 // Given an iterator as returned by performQuery(), return the read section for the record.
 295
 296 ReadSection
 297 DbConstIndex::getRecordSection(DbIndexIterator iter) const
 298 {
 299         uint32 recordNumber = mRecordNumberVector[iter - mKeyOffsetVector.begin()];
 300         return mTable.getRecordSection(recordNumber);
 301 }
 302
 303 // Construct a mutable index from a read-only index.
 304
 305 DbMutableIndex::DbMutableIndex(const DbConstIndex &index)
 306 :       DbIndex(index),
 307         mIndexDataSize(0)
 308 {
 309         // go through the const index and copy all the entries into the
 310         // mutable index
 311
 312         const ReadSection &tableSection = index.mTable.getTableSection();
 313
 314         size_t numRecords = index.mKeyOffsetVector.size();
 315         for (size_t i = 0; i < numRecords; i++) {
 316                 uint32 recordNumber = index.mRecordNumberVector.at(i);
 317                 uint32 keyOffset = index.mKeyOffsetVector.at(i);
 318                 uint32 keySize = tableSection.at(keyOffset);
 319                 DbIndexKey key(tableSection, Range(keyOffset + AtomSize, keySize), *this);
 320                 mMap.insert(IndexMap::value_type(key, recordNumber));
 321         }
 322 }
 323
 324 DbMutableIndex::DbMutableIndex(const MetaRecord &metaRecord, uint32 indexId, bool isUniqueIndex)
 325 :       DbIndex(metaRecord, indexId, isUniqueIndex),
 326         mIndexDataSize(0)
 327 {
 328 }
 329
 330 DbMutableIndex::~DbMutableIndex()
 331 {
 332 }
 333
 334 // Remove all entries for a record from an index. This is not an ideal implementation,
 335 // since it walks the entire index. In a perfect world, we'd generate all the record's
 336 // keys and lookup matching entries, deleting only those with the correct record number.
 337 // But this is not a perfect world.
 338
 339 void
 340 DbMutableIndex::removeRecord(uint32 recordNumber)
 341 {
 342         IndexMap::iterator it, temp;
 343         for (it = mMap.begin(); it != mMap.end(); ) {
 344                 temp = it; it++;
 345                 if (temp->second == recordNumber)
 346                         mMap.erase(temp);
 347         }
 348 }
 349
 350 // Insert a record into an index.
 351
 352 void
 353 DbMutableIndex::insertRecord(uint32 recordNumber, const ReadSection &packedRecord)
 354 {
 355         // The common case is that each indexed attribute has a single value in
 356         // the record; detect and handle this separately since we can avoid an
 357         // expensive recursive technique.
 358
 359         size_t numAttributes = mAttributes.size();
 360         bool allSingleValued = true;
 361
 362         for (size_t i = 0; i < numAttributes; i++) {
 363                 uint32 numValues = mAttributes[i]->getNumberOfValues(packedRecord);
 364                 if (numValues == 0) {
 365                         // record does not have value required by index; for a unique index,
 366                         // this is an error, otherwise just don't index the record
 367                         if (mIsUniqueIndex)
 368                                 CssmError::throwMe(CSSMERR_DL_MISSING_VALUE);
 369                         else
 370                                 return;
 371                 }
 372                 else if (numValues > 1) {
 373                         allSingleValued = false;
 374                         break;
 375                 }
 376         }
 377
 378         if (allSingleValued)
 379                 insertRecordSingle(recordNumber, packedRecord);
 380
 381         else {
 382                 // recursively build all appropriate index keys, and add them to the map
 383                 WriteSection keyData;
 384                 insertRecordMulti(recordNumber, packedRecord, 0, keyData, 0);
 385         }
 386 }
 387
 388 void
 389 DbMutableIndex::insertRecordSingle(uint32 recordNumber, const ReadSection &packedRecord)
 390 {
 391         // append the key values to the index data
 392         uint32 offset = mIndexDataSize;
 393         for (uint32 i = 0; i < mAttributes.size(); i++)
 394                 mAttributes[i]->copyValueBytes(0, packedRecord, mIndexData, mIndexDataSize);
 395         mIndexData.size(mIndexDataSize);
 396
 397         // make an index key
 398         DbIndexKey key(mIndexData, Range(offset, mIndexDataSize - offset), *this);
 399
 400         // if this is a unique index, check for a record with the same key
 401         if (mIsUniqueIndex && (mMap.find(key) != mMap.end()))
 402                 // the key already exists, which is an error
 403                 CssmError::throwMe(CSSMERR_DL_INVALID_UNIQUE_INDEX_DATA);
 404
 405         // insert the item into the map
 406         mMap.insert(IndexMap::value_type(key, recordNumber));
 407 }
 408
 409 void
 410 DbMutableIndex::insertRecordMulti(uint32 recordNumber, const ReadSection &packedRecord,
 411         uint32 attributeIndex, WriteSection &keyData, uint32 keySize)
 412 {
 413         const MetaAttribute &metaAttribute = *(mAttributes[attributeIndex]);
 414         uint32 numValues = metaAttribute.getNumberOfValues(packedRecord);
 415
 416         for (uint32 i = 0; i < numValues; i++) {
 417
 418                 uint32 newKeySize = keySize;
 419                 metaAttribute.copyValueBytes(i, packedRecord, keyData, newKeySize);
 420
 421                 if (attributeIndex + 1 == mAttributes.size()) {
 422                         uint32 offset = mIndexDataSize;
 423                         mIndexDataSize = mIndexData.put(mIndexDataSize, newKeySize, keyData.address());
 424                         mIndexData.size(mIndexDataSize);
 425
 426                         DbIndexKey key(mIndexData, Range(offset, mIndexDataSize - offset), *this);
 427                         if (mIsUniqueIndex && (mMap.find(key) != mMap.end()))
 428                                 CssmError::throwMe(CSSMERR_DL_INVALID_UNIQUE_INDEX_DATA);
 429
 430                         mMap.insert(IndexMap::value_type(key, recordNumber));
 431                 }
 432                 else
 433                         // otherwise, recurse with the rest of the attributes
 434                         insertRecordMulti(recordNumber, packedRecord, attributeIndex + 1, keyData, newKeySize);
 435         }
 436 }
 437
 438 uint32
 439 DbMutableIndex::writeIndex(WriteSection &ws, uint32 offset)
 440 {
 441         IndexMap::iterator it;
 442
 443         // reserve space for the index size
 444         uint32 sizeOffset = offset;
 445         offset += AtomSize;
 446
 447         offset = ws.put(offset, mIndexId);
 448         offset = ws.put(offset, mIsUniqueIndex ? 1 : 0);
 449
 450         offset = ws.put(offset, (uint32)mAttributes.size());
 451         for (uint32 i = 0; i < mAttributes.size(); i++)
 452                 offset = ws.put(offset, mAttributes[i]->attributeId());
 453
 454         offset = ws.put(offset, (uint32)mMap.size());
 455
 456         // reserve space for the array of offsets to key data
 457         uint32 keyPtrOffset = offset;
 458         offset += AtomSize * mMap.size();
 459
 460         // write the array of record numbers
 461         for (it = mMap.begin(); it != mMap.end(); it++) {
 462                 offset = ws.put(offset, it->second);
 463         }
 464
 465         // write the key data
 466         for (it = mMap.begin(); it != mMap.end(); it++) {
 467                 keyPtrOffset = ws.put(keyPtrOffset, offset);
 468                 offset = ws.put(offset, it->first.keySize());
 469                 offset = ws.put(offset, it->first.keySize(), it->first.keyData());
 470         }
 471
 472         // write the index size
 473         ws.put(sizeOffset, offset - sizeOffset);
 474
 475         return offset;
 476 }