blob: 2ecfeca4b2af4822ec4543cc679c0712f386df95 [file] [log] [blame]
// 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.
#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 {
// 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 {
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);
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