cryptohome/persistent_lookup_table.h

// Copyright 2018 The Chromium OS Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
#ifndef CRYPTOHOME_PERSISTENT_LOOKUP_TABLE_H_
#define CRYPTOHOME_PERSISTENT_LOOKUP_TABLE_H_

#include <map>
#include <string>
#include <utility>
#include <vector>

#include <base/files/file_path.h>
#include <gtest/gtest_prod.h>

#include "cryptohome/platform.h"

namespace cryptohome {

// Return values used by various functions of PersistentLookupTable.
enum PLTError {
  PLT_SUCCESS = 0,
  PLT_KEY_NOT_FOUND,
  PLT_STORAGE_ERROR,
};

// This class is used to look up and store values, given uint64_t keys.
// We use a directory to store the values.
//
// Each value is stored in a file. Each key will have a directory with the
// name being a string version of the key, and inside it
// whenever an update is made to a value, a new version is stored in a file name
// where the version number is incremented by 1.
//
// The lowest valid file version number is 1.
//
// Periodically older versions of keys will be deleted (this
// will happen only if there is > 1 version of a key).
//
// For further context, it is expected that this data structure will be used
// to store the leaf nodes of a hash tree. Each leaf node will contain sign-in
// credential meta data (this includes low-entropy (e.g PIN) as well as
// high-entropy (i.e user passphrase) credentials). Each leaf node of the hash
// tree will be referenced by a bit-string label.
//
// The key's bit-string can be used to determine the leaf's position in the hash
// tree. That, coupled with the fan-out factory of the tree (K), can be used to
// determine the labels required to compute the auxilliary hashes needed to
// determine the root hash.
//
// As an example, consider the following bit string label for a tree with
// fan-out = 4 : "0101001" By dropping the last log2(K) = 2 bits, and using the
// remainder as a prefix, we can calculate the auxiliary labels needed:
//
// "01010" + {"00", "10", "11"} = "0101000", "0101010", "0101011".
//
// These can be used to obtain the hash of inner label "01010". This step can
// then be performed recursively to obtain the root hash for label "".
//
// The values will be stored in files with names of the form "<version>.value",
// where |version| denotes the version number of that key value.
//
// NOTE: An empty value file is used as a marker that a key has been removed,
// and marked for deletion. It is forbidden to store key values which are
// empty.
class PersistentLookupTable {
 public:
  PersistentLookupTable(Platform* platform, base::FilePath basedir);
  ~PersistentLookupTable() = default;

  // Initializes the lookup table data structure and backing storage directory.
  // Load in the contents of an existing table if one already exists.
  //
  // This function also removes all old versions of all keys.
  bool InitOnBoot();

  // Retrieves a value, which will be placed in |value|, given a |key|.
  // This function returns:
  // - PLT_SUCCESS if we could successfully retrieve the key value,
  // - PLT_KEY_NOT_FOUND if |key| doesn't exist.
  // - PLT_STORAGE_ERROR for errors reading the PLT.
  //
  // The |value| vector is supplied by the caller, and is filled only when the
  // return type is PLT_SUCCESS.
  //
  // Also note that during RemoveKey(), an empty value is written to
  // the key directory to ensure that the key deletion is persisted.
  // GetValue() inspects the read |value| to make sure that it isn't the empty
  // version, and it returns PLT_KEY_NOT_FOUND if so.
  PLTError GetValue(const uint64_t key, std::vector<uint8_t>* value);

  // Stores a new value at a given key location.
  // This function returns:
  // - PLT_SUCCESS on success,
  // - PLT_STORAGE_ERROR on failure.
  //
  // It is expected that this function will persist the updated value to disk.
  PLTError StoreValue(const uint64_t key, const std::vector<uint8_t>& new_val);

  // Removes a key and its corresponding value from the look-up table.
  // All versions of the key will need to be removed from the table and
  // its associated storage.
  //
  // In order to ensure that a delete does not get lost across corruption, we
  // first write an empty file as a new version to the key directory.
  // We then invoke the directory deletion. This way, even if there was a
  // failure between creating a new file version and calling the directory
  // delete, we still have a way of ascertaining that the key has been removed.
  //
  // This function returns:
  // - PLT_SUCCESS if we are able to delete the key successfully,
  // - PLT_STORAGE_ERROR if we encountered an issue deleting the key.
  PLTError RemoveKey(const uint64_t key);

  // Returns |true| if an entry exists for |key|, and |false| otherwise.
  bool KeyExists(const uint64_t key);

  // Obtains a list of currently used keys and places them in |key_list|.
  void GetUsedKeys(std::vector<uint64_t>* key_list);

 private:
  friend class PersistentLookupTableTest;
  FRIEND_TEST(PersistentLookupTableTest, CreateDirStoreValues);
  FRIEND_TEST(PersistentLookupTableTest, RestoreTable);

  // Finds the latest verified version number for a key.
  // Returns a non-zero version number on success, 0 otherwise.
  // NOTE: We assume that the minimum version number is 1.
  // A return value of 0 may mean either:
  // - The key directory doesn't exist, or
  // - The directory exists, but no valid file exists inside it.
  uint32_t FindLatestVersion(const uint64_t key);

  // Delete all the versions of a key, except the version specified in
  // |version_to_save|. If |version_to_save| is 0, remove the entire key
  // directory.
  void DeleteOldKeyVersions(const uint64_t key, uint32_t version_to_save);

  Platform* platform_;

  // Convenience member to store the lookup table directory path.
  base::FilePath table_dir_;
};

}  // namespace cryptohome

#endif  // CRYPTOHOME_PERSISTENT_LOOKUP_TABLE_H_