New patch to review for coreboot: documentation: Add documentation for timestamp library

[Marc Jones]

Marc Jones ([e-mail]) just uploaded a new patch set to gerrit, which you can find at http://review.coreboot.org/10741

-gerrit

commit d636a46d9878e0e7c442cee31e4cfd7fe8eabe00
Author: Furquan Shaikh 
Date:   Fri Nov 14 11:57:00 2014 -0800

documentation: Add documentation for timestamp library

BUG=chrome-os-partner:32973
    BRANCH=None
    TEST=None

Original-Change-Id: I4b184ffad6fcd93d63343a9bca34ad013e9d4263
    Original-Signed-off-by: Furquan Shaikh 
    Original-Reviewed-on: https://chromium-review.googlesource.com/229861
    Original-Tested-by: Furquan Shaikh 
    Original-Reviewed-by: Aaron Durbin 
    Original-Commit-Queue: Furquan Shaikh

(cherry picked from commit 97e2a3ebd9552c2a91d9ea62be515059428631cb)
    Signed-off-by: Marc Jones

Change-Id: I6ea7237f2fa749ce3a493f378f9937e642f3b678
---
 documentation/timestamp_library.txt | 445 ++++++++++++++++++++++++++++++++++++
 1 file changed, 445 insertions(+)

diff --git a/documentation/timestamp_library.txt b/documentation/timestamp_library.txt
new file mode 100644
index 0000000..ef4f051
--- /dev/null
+++ b/documentation/timestamp_library.txt
@@ -0,0 +1,445 @@
+=========================== Table of Contents ==================================
+Introduction
+
+Data structures used
+	cache_state
+	cbmem_state
+	table
+	entries
+
+Internal Functions
+	timestamp_cache_init
+	timestamp_cache_get
+	timestamp_alloc_cbmem_table
+	timestamp_table_get
+	timestamp_add_table_entry
+
+Function APIs
+	timestamp_early_init
+	timestamp_init
+	timestamp_add
+	timestamp_add_now
+	timestamp_sync
+
+Use / Test Cases
+	Case 1: Timestamp Region Exists
+	Case 2: No timestamp region, fresh boot, cbmem_initialize called after
+	timestamp_init
+	Case 3: No timestamp region, fresh boot, cbmem_initialize called before
+	timestamp_init
+	Case 4: No timestamp region, resume, cbmem_initialize called after
+	timestamp_init
+	Case 5: No timestamp region, resume, cbmem_initialize called before
+	timestamp_init
+
+
+============================== Introduction ====================================
+
+	The aim of timestamp library is to make it easier for different boards
+to  save timestamps in cbmem / stash (until cbmem is brought up) by providing a
+simple API to initalize, add and sync timestamps. In order to make the
+timestamps persistent and accessible from the kernel, we need to ensure that all
+the saved timestamps end up in cbmem area under the CBMEM_ID_TIMESTAMP
+tag. However, until the cbmem area is available, the timestamps can be saved to
+board/SOC-defined _timestamp region or in a local stage-specific stash. The work
+of identifying the right location for storing timestamps is done by the library
+and is not exposed to the user.
+
+	Working of timestamp library from a user perspective can be outlined in
+the following steps:
+1. Initialize the _timestamp cache (if any used)
+2. Initialize the base time and reset cbmem timestamp area
+3. Start adding timestamps
+
+	Steps 1) and 2) above can be performed in a single API call as explained
+in later sections. Behind the scenes, the timestamp library takes care of:
+1. Identifying the correct location for storing timestamps (cbmem or _timestamp
+region or local stash).
+2. Once cbmem is up, ensure that all timestamps are synced from _timestamp
+region or local stash into the cbmem area.
+3. Add a new cbmem timestamp area based on whether a reset of cbmem timestamp
+region is required / not.
+
+========================== Data structures used ================================
+
+	The main structure that maintains information about the timestamp cache
+is:
+struct __attribute__((__packed__)) timestamp_cache {
+        uint16_t cache_state;
+        uint16_t cbmem_state;
+        struct timestamp_table table;
+        struct timestamp_entry entries[MAX_TIMESTAMP_CACHE];
+};
+
+1. cache_state
+	The state of the cache is maintained by cache_state attribute which can
+be any one of the following:
+
+enum {
+        TIMESTAMP_CACHE_UNINITIALIZED = 0,
+        TIMESTAMP_CACHE_INITIALIZED,
+        TIMESTAMP_CACHE_NOT_NEEDED,
+};
+
+	By default, if the cache is stored in local stash (bss area), then it
+will be reset to uninitialized state. However, if the cache is stored in
+_timestamp region, then it might have garbage in any of the attributes. Thus, if
+_timestamp region is being used by any board, it is important to call
+timestamp_early_init which provides the initialization of timestamp cache.
+
+	Once the cache is initialized, its state is set to
+cache_initialized. Henceforth, the calls to cache i.e. timestamp_add know that
+the state reflected is valid and timestamps can be directly saved in the cache.
+
+	When cbmem area is up (i.e. call to cbmem_initialize), we do not need to
+store the timestamps in local stash / _timestamp area anymore. Thus, the cache
+state is set to cache_not_needed, which allows timestamp_add to store all
+timestamps directly into cbmem area.
+
+
+2. cbmem_state
+	This attribute indicates if we need to reset the timestamp area in
+cbmem. This needs to be done for fresh boot (when there is no timestamp area
+allocated in cbmem) or during resume (to clean out timestamps from earlier
+boot). This can be set to any one of the following values:
+
+enum {
+        TIMESTAMP_CBMEM_RESET_NOT_REQD = 0,
+        TIMESTAMP_CBMEM_RESET_REQD,
+};
+
+	If _timestamp region is being used, the call to timestamp_early_init
+sets this field to reset_reqd. If this region is not being used, then instead
+the call to timestamp_init sets this field to reset_reqd. Thus, when cbmem
+initialization is complete, the timestamp library ensures that the cbmem
+timestamp area is properly set as per the value of this attribute and resets
+this field to reset_not_reqd. In case of resume path, this field would be set
+accordingly by timestamp_early_init  / timestamp_init thus ensuring that
+timestamps from earlier boot dont float around into current boot logs. Also,
+during early ramstage, when cbmem is not yet up, local stash would be used which
+is in the bss area and thus this field is set to reset_not_reqd (unless
+timestamp_init is called before or after cbmem_intiialize). Hence, when ramstage
+brings up cbmem and syncs timestamps, the cbmem timestamp area is not reset. If
+ramstage is the first stage where timestamp_init is called, then the cbmem area
+is accordingly reset in timestamp_sync  or timestamp_init based on the order in
+which calls are made. Details are explained in the use cases towards the end.
+
+
+3. table
+	This field is represented by a structure which provides overall
+information  about the entries in the timestamp area:
+
+struct timestamp_table {
+        uint64_t        base_time;
+        uint32_t        max_entries;
+        uint32_t        num_entries;
+        struct timestamp_entry entries[0]; /* Variable number of entries */
+} __attribute__((packed));
+
+	It indicates the base time for all timestamp entries, maximum number of
+entries that can be stored, total number of entries that currently exist and an
+entry structure to hold variable number of entries.
+
+
+4. entries
+	This field holds the details of each timestamp entry, upto a maximum of
+MAX_TIMESTAMP_CACHE which is defined as 16 entries. Each entry is defined by:
+
+struct timestamp_entry {
+        uint32_t        entry_id;
+        uint64_t        entry_stamp;
+} __attribute__((packed));
+
+	entry_id holds the timestamp id corresponding to this entry and
+entry_stamp holds the actual timestamp.
+
+
+	For timestamps stored in the cbmem area, a timestamp_table is allocated
+with space for MAX_TIMESTAMPS equal to 30. Thus, the cbmem area holds base_time,
+max_entries (which is 30), current number of entries and the actual entries
+represented by timestamp_entry.
+
+
+========================== Internal Functions ==================================
+
+1. timestamp_cache_init
+	Initializes the timestamp cache to a known state by setting num_entries
+to 0, base_entries to MAX_TIMESTAMP_CACHE, base_time to caller-provided base,
+cache_state to TIMESTAMP_CACHE_INITIALIZED and cbmem_state to caller-provided
+state.
+
+
+2.  timestamp_cache_get
+	This function returns a pointer to timestamp cache. It basically
+identifies what cache to use based on following parameters:
+a. If __PRE_RAM__ is true i.e. we are in pre-ramstage step and _timestamp region
+is provided, use _timestamp region.
+b. Otherwise use local stash
+
+	If using _timestamp region, it ensures that the size of the region is
+big enough to hold all of timestamp_cache structure and MAX_TIMESTAMP_CACHE
+timestamp entries. Once the location of cache is decided, it checks to see if
+cache is not yet initialized, and calls timestamp_cache_init if required.
+
+
+3. timestamp_alloc_cbmem_table
+	This function exists only in romstage and ramstage since only these two
+stages access cbmem area. It allocates a new table for MAX_TIMESTAMPS number of
+entries in the cbmem area using CBMEM_ID_TIMESTAMP tag. It also resets the
+base_time and num_entries to 0.
+
+
+4. timestamp_table_get
+	This function returns a pointer to the timestamp table. Based on the
+value of cache_state in timestamp_cache, it provides a pointer either to the
+cache (in stash or _timestamp region) or the cbmem timestamp table. If a pointer
+to the cbmem timestamp table is returned, it checks to see if cbmem_state
+indicates a reset of the cbmem timestamp area. If required, it makes a call to
+timestamp_alloc_cbmem_table.
+
+
+5. timestamp_add_table_entry
+	This function adds a new entry to the timestamp table obtained by making
+a call to timestamp_table_get. It sets the id based on user-provided id and the
+stamp is set to user-provided time - table base time. This is to normalize all
+the timestamps.
+
+
+============================= Function APIs ====================================
+
+1. timestamp_early_init
+	It is essential to call this function only if _timestamp region is being
+used. This should be the first call made to the timestamp library. Since
+_timestamp region can contain arbitary values in the different fields of the
+cache, this function initializes the fields properly by calling
+timestamp_cache_init with the cache pointer, user-provided base time and
+cbmem_state as TIMESTAMP_CBMEM_RESET_REQD. This will provide an indication that
+cbmem timestamp area needs to be added (in case of fresh boot) or reset to 0
+entries(in case of resume).
+
+
+2. timestamp_init
+	It is essential to call this function before any call to timestamp_add
+is made. In case of _timestamp region being used, only a call to
+timestamp_early_init is required. In all other cases, it is essential to call
+timestamp_init to set the cbmem_state to TIMESTAMP_CBMEM_RESET_REQD. This will
+provide an indication that cbmem timestamp area needs to be added (in case of
+fresh boot) or reset to 0 entries(in case of resume).
+
+
+3. timestamp_add
+	This function accepts from user a timestamp id and time to record in the
+timestamp table. Based on the table provided by timestamp_table_get, it stores
+the entry in the appropriate table in cbmem or _timestamp region or local
+stash.
+
+
+4. timestamp_add_now
+	This function calls timestamp_add with user-provided id and current
+time.
+
+
+5. timestamp_sync
+	This is one of the most important functions required to ensure the
+proper functioning of the timestamp library across cbmem, _timestamp region and
+local stash with minimal interference for the user. It is important to note that
+this function is called only by cbmem_initialize to ensure that once the cbmem
+area is ready, we automatically sync all the timestamps saved in the cache to
+cbmem area. Thus, the user never has to call the timestamp_sync function.
+
+	This function checks to see if the cache state indicates that a cbmem
+reset of timestamp area is required or no timestamp area exists in cbmem at
+all. In that case, it allocates a new cbmem area by calling
+timestamp_alloc_cbmem_table.
+
+	Otherwise, it uses cbmem_find to use the timestamp area in cbmem. It
+then uses timestamp_add_table_entry to move all the entries from cache to cbmem
+area. Here, two cases can occur with respect to the base time subtraction:
+
+a. Newly added cbmem table will have a base time of 0. Thus, no adjustments are
+required for the timestamps being added from cache to cbmem table.
+
+b. Timestamps added to cache before ramstage: In this case, the base time in
+cache table will be 0 and timestamp_add_table_entry will take care of
+subtracting the correct base_time. Finally, it resets the timestamp cache to:
+
+        cache_state: TIMESTAMP_CACHE_NOT_NEEDED
+        cbmem_state: TIMESTAMP_CBMEM_RESET_NOT_REQD
+        num_entries: 0
+
+	Also, the base_time in cbmem table is update if it is currently zero
+indicating that it needs to inherit base time from cache table since
+cbmem table might be newly allocated.
+
+
+============================= Use / Test Cases =================================
+
+	The following cases have been considered while designing the timestamp
+library. It is important to ensure that any changes made to this library satisfy
+each of the following use cases:
+
+Case 1: Timestamp Region Exists (Fresh Boot / Resume)
+
+
+1. timestamp_early_init is called to setup the cache state and cbmem_state is
+set to reset_reqd. These properties are set in the timestamp cache which is part
+of _timestamp region.
+
+2. <Any number of timestamp_add / timestamp_add_now> : All saved in _timestamp
+region
+
+3. Once cbmem_initiliaze is complete, it calls timestamp_sync, which checks the
+_timestamp region to check the cbmem_state field. Since it says reset_reqd, a
+new area for timestamp is setup in cbmem by calling cbmem_add. The value of
+cbmem_state is set to reset_not_reqd in _timestamp region cache.
+
+4. After entering ramstage, the local stash acts as the timestamp cache. Since
+it is in BSS area, the cache_state field is set to uninitialized and cbmem_state
+field is set to reset_not_reqd.
+
+5. On any call to timestamp_add / timestamp_add_now, it initializes the cache
+and sets cache_state field to initialized whereas cbmem_state is still set to
+reset_not_reqd.
+
+6. Once cbmem_initiliaze is complete, it calls timestamp_sync, which checks the
+local stash to check the cbmem_state field. Since it says reset_not_reqd, it
+uses cbmem_find to find already allocated timestamp area in cbmem. If none is
+found, it allocates a new one.
+
+7. <Any number of calls to timestamp_add / timestamp_add_now> : All saved in
+cbmem
+
+
+Case 2: No timestamp region, fresh boot, cbmem_initialize called after
+timestamp_init
+
+1. Since timestamp_init is called before cbmem_initialize, it will set the cache
+field attributes to: cache_state as initialized and cbmem_state as
+reset_reqd. This ensures that timestamp_sync sets up a new cbmem area for
+timestamps.
+
+2. < Any number of calls to timestamp_add / timestamp_add_now> : All saved in
+stash
+
+3. Once cbmem_initiliaze is complete, it calls timestamp_sync, which checks the
+stash cache to check the cbmem_state field. Since it says reset_reqd, a new area
+for timestamp is setup in cbmem by calling cbmem_add. The value of cbmem_state
+is set to reset_not_reqd in stash cache.
+
+4. After entering ramstage, a new local stash acts as the timestamp cache. Since
+it is in BSS area, the cache_state field is set to uninitialized and cbmem_state
+field is set to reset_not_reqd.
+
+5. On any call to timestamp_add / timestamp_add_now, it initializes the cache
+and sets cache_state field to initialized whereas cbmem_state is still set to
+reset_not_reqd.
+
+6. Once cbmem_initiliaze is complete, it calls timestamp_sync, which checks the
+local stash to check the cbmem_state field. Since it says reset_not_reqd, it
+uses cbmem_find to find already allocated timestamp area in cbmem. If none is
+found, it allocates a new one.
+
+7. <Any number of calls to timestamp_add / timestamp_add_now> : All saved in
+cbmem
+
+
+Case 3: No timestamp region, fresh boot, cbmem_initialize called before
+timestamp_init
+
+1. Since cbmem_initialize is called before timestamp_init, it will call
+timestamp_sync which checks local stash to check for cbmem_state field. Since,
+cbmem_state says no_reset_reqd, it uses cbmem_find to look for a timestamp area
+in cbmem. Since, it is a fresh boot, none will be found and it uses cbmem_add to
+create a new area on cbmem.
+
+2. timestamp_init is called, which sets local cache state to reset required. It
+then calls timestamp_table_get which sees that cache_state is cache_not_needed
+and cbmem_state is reset_reqd. Thus, it calls timestamp_alloc_cbmem_table to
+reset the cbmem area which is as good as no change in the state of cbmem
+area. Then, the cbmem_state is set to reset_not_reqd.
+
+3. <Any number of calls to timestamp_add / timestamp_add_now> : All saved in
+cbmem
+
+4. After entering ramstage, a new local stash acts as the timestamp cache. Since
+it is in BSS area, the cache_state field is set to uninitialized and cbmem_state
+field is set to reset_not_reqd.
+
+5. On any call to timestamp_add / timestamp_add_now, it initializes the cache
+and sets cache_state field to initialized whereas cbmem_state is still set to
+reset_not_reqd.
+
+6. Once cbmem_initiliaze is complete, it calls timestamp_sync, which checks the
+local stash to check the cbmem_state field. Since it says reset_not_reqd, it
+uses cbmem_find to find already allocated timestamp area in cbmem. If none is
+found, it allocates a new one.
+
+7. <Any number of calls to timestamp_add / timestamp_add_now> : All saved in
+cbmem
+
+
+Case 4: No timestamp region, resume, cbmem_initialize called after
+timestamp_init
+
+1. Since timestamp_init is called before cbmem_initialize, it will set the cache
+field attributes to: cache_state as initialized and cbmem_state as reset_reqd.
+
+2. < Any number of calls to timestamp_add / timestamp_add_now> : All saved in
+stash
+
+3. Once cbmem_initiliaze is complete, it calls timestamp_sync, which checks the
+stash cache to check the cbmem_state field. Since it says reset_reqd,
+timestamp_sync resets cbmem area to num_entries=0, thus flushing timestamps from
+earlier boot. The value of cbmem_state is set to reset_not_reqd in stash cache.
+
+4. After entering ramstage, a new local stash acts as the timestamp cache. Since
+it is in BSS area, the cache_state field is set to uninitialized and cbmem_state
+field is set to reset_not_reqd.
+
+5. On any call to timestamp_add / timestamp_add_now, it initializes the cache
+and sets cache_state field to initialized whereas cbmem_state is still set to
+reset_not_reqd.
+
+6. Once cbmem_initiliaze is complete, it calls timestamp_sync, which checks the
+local stash to check the cbmem_state field. Since it says reset_not_reqd, it
+uses cbmem_find to find already allocated timestamp area in cbmem. If none is
+found, it allocates a new one.
+
+7. <Any number of calls to timestamp_add / timestamp_add_now> : All saved in
+cbmem
+
+
+Case 5: No timestamp region, resume, cbmem_initialize called before
+timestamp_init
+
+1. Since cbmem_initialize is called before timestamp_init, it will call
+timestamp_sync which checks local stash to check for cbmem_state field. Since,
+cbmem_state says no_reset_reqd, it uses cbmem_find to look for a timestamp area
+in cbmem. Since, it is resume, it will find the older cbmem timestamp area from
+earlier boot. However, nothing is added to cbmem area since timestamp_add /
+timestamp_add_now is expected to be used only after call to timestamp_init.
+
+2. timestamp_init is called, which sets local cache state to reset required. It
+then calls timestamp_table_get which sees that cache_state is cache_not_needed
+and cbmem_state is reset_reqd. Thus, it calls timestamp_alloc_cbmem_table to
+reset the cbmem area which sets num_entries to 0. Thus, flushing timestamps from
+earlier boot. Then, the cbmem_state is set to reset_not_reqd.
+
+3. <Any number of calls to timestamp_add / timestamp_add_now> : All saved in
+cbmem
+
+4. After entering ramstage, a new local stash acts as the timestamp cache. Since
+it is in BSS area, the cache_state field is set to uninitialized and cbmem_state
+field is set to reset_not_reqd.
+
+5. On any call to timestamp_add / timestamp_add_now, it initializes the cache
+and sets cache_state field to initialized whereas cbmem_state is still set to
+reset_not_reqd.
+
+6. Once cbmem_initiliaze is complete, it calls timestamp_sync, which checks the
+local stash to check the cbmem_state field. Since it says reset_not_reqd, it
+uses cbmem_find to find already allocated timestamp area in cbmem. If none is
+found, it allocates a new one.
+
+7. <Any number of calls to timestamp_add / timestamp_add_now> : All saved in
+cbmem