aboutsummaryrefslogblamecommitdiff
path: root/ks_flash.c
blob: 0d8542e00173f7abb194e2d084144ac0f209d5e7 (plain) (tree)
1
2
3
4
5
6
7
1547
1548
1549
1550
1551
1552
1553
1554
1555
1556
1557
1558
1559
1560
1561
1562
1563
1564
1565
1566
1567
1568
1569
1570
1571
1572
1573
1574
1575
1576
1577
1578
1579
1580
1581
1582
1583
1584
1585
1586
1587
1588
1589
1590
1591
1592
1593
1594
1595
1596
1597
1598
1599
1600
1601
1602
1603
1604
1605
1606
1607
1608
1609
1610
1611
1612
1613
1614
1615
1616
1617
1618
1619
1620
1621
1622
1623
1624
1625
1626
1627
1628
1629
1630
1631
1632
1633
1634
1635
1636
1637
1638
1639
1640
1641
1642
1643
1644
1645
1646
1647
1648
1649
1650
1651
1652
1653
1654
1655
1656
1657
1658
1659
1660
1661
1662
1663
1664
1665
1666
1667
1668
1669
1670
1671
1672
1673
1674
1675
1676
1677
1678
1679
1680
1681
1682
1683
1684
1685
1686
1687
1688
1689
1690
1691
1692
1693
1694
1695
1696
1697
1698
1699
1700
1701
1702
1703
1704
1705
1706
1707
1708
1709
1710
1711
1712
1713
1714
1715
1716
1717
1718
1719
1720
1721
1722
1723
1724
1725
1726
1727
1728
1729
1730
1731
1732
1733
1734
1735
1736
1737
1738
1739
1740
1741
1742
1743
1744
1745
1746
1747
1748
1749
1750
1751
1752
1753
1754
1755
1756
1757
1758
1759
1760
1761
1762
1763
1764
1765
1766
1767
1768
1769
1770
1771
1772
1773
1774
1775
1776
1777
1778
1779
1780
1781
1782
1783
1784
1785
1786
1787
1788
1789
1790
1791
1792
1793
1794
1795
1796
1797
1798
1799
1800
1801
1802
1803
1804
1805
1806
1807
1808
1809
1810
1811
1812
1813
1814
1815
1816
1817
1818
1819
1820
1821
1822
1823
1824
1825
1826
1827
1828
1829
1830
1831
1832
1833
1834
1835
1836
1837
1838
1839
1840
1841
1842
1843
1844
1845
1846
1847
1848
1849
1850
1851
1852
1853
1854
1855
1856
1857
1858
1859
1860
1861
1862
1863
1864
1865
1866
1867
1868
1869
1870
1871
1872
1873
1874
1875
1876
1877
1878
1879
1880
1881
1882
1883
1884
1885
1886
1887
1888
1889
1890
1891
1892
1893
1894
1895
1896
1897
1898
1899
1900
1901
1902
1903
1904
1905
1906
1907
1908
1909
1910
1911
1912
1913
1914
1915
1916
1917
1918
1919
1920
1921
1922
1923
1924
1925
1926
1927
1928
1929
1930
1931
1932
1933
1934
1935
1936
1937
1938
1939
1940
1941
1942
1943
1944
1945
1946
1947
1948
1949
1950
1951
1952
1953
1954
1955
1956
1957
1958
1959
1960
1961
1962
1963
1964
1965
1966
1967
1968
1969
1970
1971
1972
1973
1974
1975
1976
1977
1978
1979
1980
1981
1982
1983
1984
1985
1986
1987
1988
1989
1990
1991
1992
1993
1994
1995
1996
1997
1998




                                           

                                                             



























                                                                           



                   

                         

                                   
 

                          

             
  

                      
                                                                   




                                                                     


              

                                                                              
                                                              
                                                                                          
                                                      
                                                                                  

                     
  











                                                                                        
   
 
                




                                     
                       
 
  
                                                                           
   
 






                                

                                                                                       
                    
 
















                                                                                             



                                                              
 









                                        
 
                                  
 


                   
 
               




                                                               

                
  










                              
  

                                                                                    

   



                             
                                                       
 
                





                                                                                  
                               
       
 



                                                                         
 


                                         


                                                                      
   

               
 
  
                   
   
 
                                                                                  
 

                                                       

 





                                                                                      


                                                                  
                                                                      




                                                                      
 


                          
                                                 













                                                          
 
 




                                                                            
 
                                               



                                       
 


                                                               
 

                                                                                             
                                                 






                                       
 


                                            
 




                                                                   
 



                                                     

                                                             
   
 


                                                                         
 
                                     
 




                                                             
 



                                                                          
                                                                        
 

                                 
 
  
                          

   
                                                           
 
                                           
 
 
  

                      

                                                                   
   
 
                                                                           
 

                                                                                                
 
                                        


                                                  
                                     
 



                                  

                      
                       
          






                                             
          
          
                                             
   






                                                                    



                                                      
 
 
















                                                                                   
                                     

 
  


                                                                      

   
                                                          
 
                                  
                                
 

                                               




                                                          
 
                                                

                                        
                                                           
                                     

                

 
  
                                                                     


                                                     
 


                                  
                                         
 
                                        
                                                                          

                                     



                
                                                             



                                                      

                                  
 
                                        
                                                       


                                     


  
                                                        
                                                          




                                                                      
   
 
                                                            
 


                                  








                                                                                                    
 
                                                      


  













                                                                                                

                      
                       













                                                                                    




























                                                                                               









                                                                       

   









                                                                       


                                                                
                                       

     


                                                             





                                                 
                             

                      


                                                                               
                                  



                                                                       
 
                                               







                                                                    

                                                      

                                          








                                              



                                                                    

       
                               

                                                                                      
                                          






                                             



                             
                                                

            
                                             
     
 



                                                          
                                                                


                       


                                                                      

       










                                                                      

                                                       
     






                                     





                                                                      



                                              
                                              



                                                         
                                              



                                          
                                              



                                              
                                               




                              
                          





                                                    




                                                                     

























                                                                      


                                              
 

                                                  
 


                                           
 
                                                                                              

                 



                                                                                            
 











                                                                    
 
                                                      
 

                                           
 
                                                 

                   














                                                                                                
 











                                               
 







                                               
     
 







                                                                                               
 









                                                                                               

                                           




                                                     


                                                                                  

                                              
                                           
     
   
 


















                                                                      
 


                                        
 
                                                


                                                   
 
                                                            

                                       
 
                                                                            



                              
                                



























                                                                     
                
 
 


                                                                
                                                  

                                   
               
                

 
                                         
 

                                   
 
                
 
 











                                                                
 
                                         
                                                  
                                                                            
 








                                                                                                      
 

                                
 
                                                                                   




                                      
 
                                              



                                                 



                           
                                          
                        






                                                                                 




                                              
                                                                         
             
 
 



                                                                                
                                   
                                   
 



                       

                                                                                      

               
                                              
                                                                             
 
                            
 
                                     
 
                        
















                                     
                                                                      



                                                                                    
                      


                 



                                          
                                                   




                                   
             
 
                                                                                                  

               
                
 
                                                                                                 

               
                             
                                          

                             

                                           

                                                      


                                        

                                                              






                                                           

                       
 

                  
                                         



                                       
 

                                                       
 
                                                                                
               
 



                                                 


                   
                

 

                                                                                       
                                                                 





                                                                               
                                                                               
                                            





                                                                 
                                                                               
                                             






                                                         
                                         

                                                               


                                                         
                                                                       



                                                          
                                                                   
 











                                                                    




                                                               

               
                                                         























                                                                            
                          




                                                                              

                                                   
 

                                                                                               
 
                                                              
 
                            
                     








                                                                                  









                                                                              
                                               



                  
                







                                                                 


























                                                                                      
                        





                                                                                          

                                                   

                 
                                                                                             

                 
                                                                                                      
 
                                                     

























                                                                      



                                                                    






                                                                                                  


                                                                              











                                                                   
                        




                                                                                          



                                                                                                      









                                                                                            

































                                                                                                    




                                                    








                                                            






















                                                                                      

                              

                          
                        
 
                                                                                          

                 

                        
 
                                               
 
                                                                                           

                 


                                                           















                                                                    





                                                             





























                                                                                      
                        





                                                                                          
                        

               

                                               

                 

                                                                                                       

                 
                                    







                                                                            

 



































































































































































































































































































































































































































































                                                                                                   







                                                 



                   



                      

   
  


                                                                         

   





                                                                    
 
                  

                                   





                                                       
 

                
 
  

                                                                     
   
 

                                                                      
                    
                                

                  

               
 




                                                                             
               
 
                              
 
                                               
                                
 




                                                                     


                                                                      
   
 
                                                     


                                                                             
                                                                                   
                                
 
               
 
                         
 
                                                     

 





                                                       
 
                  

                                   


                       
 

                                                    
 

                                          
 





                                                                            
 

                                   
 

                                                              
 
             

 
                               
 


                                                             




                                                                     





                                                                      
                                                              
 
                                       
                                          
 


                       
 

                                                    
 


                                          


                                     
                

 
                                                                            
 
                  

                                   

                                          
 





                                                    
 
                                          
 

                                   
 

                                               
 







                                                 
 








                                                    

 

                                        
 




                        
/*
 * ks_flash.c
 * ----------
 * Keystore implementation in flash memory.
 *
 * Authors: Rob Austein, Fredrik Thulin
 * Copyright (c) 2015-2016, NORDUnet A/S All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are
 * met:
 * - Redistributions of source code must retain the above copyright notice,
 *   this list of conditions and the following disclaimer.
 *
 * - Redistributions in binary form must reproduce the above copyright
 *   notice, this list of conditions and the following disclaimer in the
 *   documentation and/or other materials provided with the distribution.
 *
 * - Neither the name of the NORDUnet nor the names of its contributors may
 *   be used to endorse or promote products derived from this software
 *   without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
 * IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
 * PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
 * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

#include <stddef.h>
#include <string.h>
#include <assert.h>

#include "hal.h"
#include "hal_internal.h"

#include "last_gasp_pin_internal.h"

#define HAL_OK CMIS_HAL_OK
#include "stm-keystore.h"
#undef HAL_OK

/*
 * Known block states.
 *
 * C does not guarantee any particular representation for enums, so
 * including enums directly in the block header isn't safe.  Instead,
 * we use an access method which casts when reading from the header.
 * Writing to the header isn't a problem, because C does guarantee
 * that enum is compatible with *some* integer type, it just doesn't
 * specify which one.
 */

typedef enum {
  BLOCK_TYPE_ERASED  = 0xFF, /* Pristine erased block (candidate for reuse) */
  BLOCK_TYPE_ZEROED  = 0x00, /* Zeroed block (recently used) */
  BLOCK_TYPE_KEY     = 0x55, /* Block contains key material */
  BLOCK_TYPE_ATTR    = 0x66, /* Block contains key attributes (overflow from key block) */
  BLOCK_TYPE_PIN     = 0xAA, /* Block contains PINs */
  BLOCK_TYPE_UNKNOWN = -1,   /* Internal code for "I have no clue what this is" */
} flash_block_type_t;

/*
 * Block status.
 */

typedef enum {
  BLOCK_STATUS_LIVE      = 0x66, /* This is a live flash block */
  BLOCK_STATUS_TOMBSTONE = 0x44, /* This is a tombstone left behind during an update  */
  BLOCK_STATUS_UNKNOWN   = -1,   /* Internal code for "I have no clue what this is" */
} flash_block_status_t;

/*
 * Common header for all flash block types.
 * A few of these fields are deliberately omitted from the CRC.
 */

typedef struct {
  uint8_t               block_type;
  uint8_t               block_status;
  uint8_t               total_chunks;
  uint8_t               this_chunk;
  hal_crc32_t           crc;
} flash_block_header_t;

/*
 * Key block.  Tail end of "der" field (after der_len) used for attributes.
 */

typedef struct {
  flash_block_header_t  header;
  hal_uuid_t            name;
  hal_key_type_t        type;
  hal_curve_name_t      curve;
  hal_key_flags_t       flags;
  size_t                der_len;
  unsigned              attributes_len;
  uint8_t               der[];  /* Must be last field -- C99 "flexible array member" */
} flash_key_block_t;

#define SIZEOF_FLASH_KEY_BLOCK_DER \
  (KEYSTORE_SUBSECTOR_SIZE - offsetof(flash_key_block_t, der))

/*
 * Key attribute overflow block (attributes which don't fit in der field of key block).
 */

typedef struct {
  flash_block_header_t  header;
  hal_uuid_t            name;
  unsigned              attributes_len;
  uint8_t               attributes[]; /* Must be last field -- C99 "flexible array member" */
} flash_attributes_block_t;

#define SIZEOF_FLASH_ATTRIBUTE_BLOCK_ATTRIBUTES \
  (KEYSTORE_SUBSECTOR_SIZE - offsetof(flash_attributes_block_t, attributes))

/*
 * PIN block.  Also includes space for backing up the KEK when
 * HAL_MKM_FLASH_BACKUP_KLUDGE is enabled.
 */

typedef struct {
  flash_block_header_t  header;
  hal_ks_pin_t          wheel_pin;
  hal_ks_pin_t          so_pin;
  hal_ks_pin_t          user_pin;
#if HAL_MKM_FLASH_BACKUP_KLUDGE
  uint32_t              kek_set;
  uint8_t               kek[KEK_LENGTH];
#endif
} flash_pin_block_t;

#define FLASH_KEK_SET   0x33333333

/*
 * One flash block.
 */

typedef union {
  uint8_t                       bytes[KEYSTORE_SUBSECTOR_SIZE];
  flash_block_header_t          header;
  flash_key_block_t             key;
  flash_attributes_block_t      attr;
  flash_pin_block_t             pin;
} flash_block_t;

/*
 * In-memory cache.
 */

typedef struct {
  unsigned            blockno;
  uint32_t            lru;
  flash_block_t       block;
} cache_block_t;

/*
 * In-memory database.
 *
 * The top-level structure is a static variable; the arrays are allocated at runtime
 * using hal_allocate_static_memory() because they can get kind of large.
 */

#ifndef KS_FLASH_CACHE_SIZE
#define KS_FLASH_CACHE_SIZE 4
#endif

#define NUM_FLASH_BLOCKS        KEYSTORE_NUM_SUBSECTORS

typedef struct {
  hal_ks_t              ks;                  /* Must be first (C "subclassing") */
  hal_ks_index_t        ksi;
  hal_ks_pin_t          wheel_pin;
  hal_ks_pin_t          so_pin;
  hal_ks_pin_t          user_pin;
  uint32_t              cache_lru;
  cache_block_t         *cache;
} db_t;

/*
 * PIN block gets the all-zeros UUID, which will never be returned by
 * the UUID generation code (by definition -- it's not a version 4 UUID).
 */

const static hal_uuid_t pin_uuid = {{0}};

/*
 * The in-memory database structure itself is small, but the arrays it
 * points to are large enough that they come from SDRAM allocated at
 * startup.
 */

static db_t db;

/*
 * Type safe casts.
 */

static inline flash_block_type_t block_get_type(const flash_block_t * const block)
{
  assert(block != NULL);
  return (flash_block_type_t) block->header.block_type;
}

static inline flash_block_status_t block_get_status(const flash_block_t * const block)
{
  assert(block != NULL);
  return (flash_block_status_t) block->header.block_status;
}

/*
 * Pick unused or least-recently-used slot in our in-memory cache.
 *
 * Updating lru values is caller's problem: if caller is using a cache
 * slot as a temporary buffer and there's no point in caching the
 * result, leave the lru values alone and the right thing will happen.
 */

static inline flash_block_t *cache_pick_lru(void)
{
  uint32_t best_delta = 0;
  int      best_index = 0;

  for (int i = 0; i < KS_FLASH_CACHE_SIZE; i++) {

    if (db.cache[i].blockno == ~0)
      return &db.cache[i].block;

    const uint32_t delta = db.cache_lru - db.cache[i].lru;
    if (delta > best_delta) {
      best_delta = delta;
      best_index = i;
    }

  }

  db.cache[best_index].blockno = ~0;
  return &db.cache[best_index].block;
}

/*
 * Find a block in our in-memory cache; return block or NULL if not present.
 */

static inline flash_block_t *cache_find_block(const unsigned blockno)
{
  for (int i = 0; i < KS_FLASH_CACHE_SIZE; i++)
    if (db.cache[i].blockno == blockno)
      return &db.cache[i].block;
  return NULL;
}

/*
 * Mark a block in our in-memory cache as being in current use.
 */

static inline void cache_mark_used(const flash_block_t * const block, const unsigned blockno)
{
  for (int i = 0; i < KS_FLASH_CACHE_SIZE; i++) {
    if (&db.cache[i].block == block) {
      db.cache[i].blockno = blockno;
      db.cache[i].lru = ++db.cache_lru;
      return;
    }
  }
}

/*
 * Release a block from the in-memory cache.
 */

static inline void cache_release(const flash_block_t * const block)
{
  if (block != NULL)
    cache_mark_used(block, ~0);
}

/*
 * Generate CRC-32 for a block.
 *
 * This function needs to understand the structure of
 * flash_block_header_t, so that it can skip over fields that
 * shouldn't be included in the CRC.
 */

static hal_crc32_t calculate_block_crc(const flash_block_t * const block)
{
  assert(block != NULL);

  hal_crc32_t crc = hal_crc32_init();

  crc = hal_crc32_update(crc, &block->header.block_type,
                         sizeof(block->header.block_type));

  crc = hal_crc32_update(crc, &block->header.total_chunks,
                         sizeof(block->header.total_chunks));

  crc = hal_crc32_update(crc, &block->header.this_chunk,
                         sizeof(block->header.this_chunk));

  crc = hal_crc32_update(crc, block->bytes + sizeof(flash_block_header_t),
                         sizeof(*block) - sizeof(flash_block_header_t));

  return hal_crc32_finalize(crc);
}

/*
 * Calculate block offset.
 */

static inline uint32_t block_offset(const unsigned blockno)
{
  return blockno * KEYSTORE_SUBSECTOR_SIZE;
}

/*
 * Read a flash block.
 *
 * Flash read on the Alpha is slow enough that it pays to check the
 * first page before reading the rest of the block.
 */

static hal_error_t block_read(const unsigned blockno, flash_block_t *block)
{
  if (block == NULL || blockno >= NUM_FLASH_BLOCKS || sizeof(*block) != KEYSTORE_SUBSECTOR_SIZE)
    return HAL_ERROR_IMPOSSIBLE;

  /* Sigh, magic numeric return codes */
  if (keystore_read_data(block_offset(blockno),
                         block->bytes,
                         KEYSTORE_PAGE_SIZE) != 1)
    return HAL_ERROR_KEYSTORE_ACCESS;

  switch (block_get_type(block)) {
  case BLOCK_TYPE_ERASED:
  case BLOCK_TYPE_ZEROED:
    return HAL_OK;
  case BLOCK_TYPE_KEY:
  case BLOCK_TYPE_PIN:
  case BLOCK_TYPE_ATTR:
    break;
  default:
    return HAL_ERROR_KEYSTORE_BAD_BLOCK_TYPE;
  }

  switch (block_get_status(block)) {
  case BLOCK_STATUS_LIVE:
  case BLOCK_STATUS_TOMBSTONE:
    break;
  default:
    return HAL_ERROR_KEYSTORE_BAD_BLOCK_TYPE;
  }

  /* Sigh, magic numeric return codes */
  if (keystore_read_data(block_offset(blockno) + KEYSTORE_PAGE_SIZE,
                         block->bytes + KEYSTORE_PAGE_SIZE,
                         sizeof(*block) - KEYSTORE_PAGE_SIZE) != 1)
    return HAL_ERROR_KEYSTORE_ACCESS;

  if (calculate_block_crc(block) != block->header.crc)
    return HAL_ERROR_KEYSTORE_BAD_CRC;

  return HAL_OK;
}

/*
 * Read a block using the cache.  Marking the block as used is left
 * for the caller, so we can avoid blowing out the cache when we
 * perform a ks_list() operation.
 */

static hal_error_t block_read_cached(const unsigned blockno, flash_block_t **block)
{
  if (block == NULL)
    return HAL_ERROR_IMPOSSIBLE;

  if ((*block = cache_find_block(blockno)) != NULL)
    return HAL_OK;

  if ((*block = cache_pick_lru()) == NULL)
    return HAL_ERROR_IMPOSSIBLE;

  return block_read(blockno, *block);
}

/*
 * Convert a live block into a tombstone.  Caller is responsible for
 * making sure that the block being converted is valid; since we don't
 * need to update the CRC for this, we just modify the first page.
 */

static hal_error_t block_deprecate(const unsigned blockno)
{
  if (blockno >= NUM_FLASH_BLOCKS)
    return HAL_ERROR_IMPOSSIBLE;

  uint8_t page[KEYSTORE_PAGE_SIZE];
  flash_block_header_t *header = (void *) page;
  uint32_t offset = block_offset(blockno);

  /* Sigh, magic numeric return codes */
  if (keystore_read_data(offset, page, sizeof(page)) != 1)
    return HAL_ERROR_KEYSTORE_ACCESS;

  header->block_status = BLOCK_STATUS_TOMBSTONE;

  /* Sigh, magic numeric return codes */
  if (keystore_write_data(offset, page, sizeof(page)) != 1)
    return HAL_ERROR_KEYSTORE_ACCESS;

  return HAL_OK;
}

/*
 * Zero (not erase) a flash block.  Just need to zero the first page.
 */

static hal_error_t block_zero(const unsigned blockno)
{
  if (blockno >= NUM_FLASH_BLOCKS)
    return HAL_ERROR_IMPOSSIBLE;

  uint8_t page[KEYSTORE_PAGE_SIZE] = {0};

  /* Sigh, magic numeric return codes */
  if (keystore_write_data(block_offset(blockno), page, sizeof(page)) != 1)
    return HAL_ERROR_KEYSTORE_ACCESS;

  return HAL_OK;
}

/*
 * Erase a flash block.  Also see block_erase_maybe(), below.
 */

static hal_error_t block_erase(const unsigned blockno)
{
  if (blockno >= NUM_FLASH_BLOCKS)
    return HAL_ERROR_IMPOSSIBLE;

  /* Sigh, magic numeric return codes */
  if (keystore_erase_subsectors(blockno, blockno) != 1)
    return HAL_ERROR_KEYSTORE_ACCESS;

  return HAL_OK;
}

/*
 * Erase a flash block if it hasn't already been erased.
 * May not be necessary, trying to avoid unnecessary wear.
 *
 * Unclear whether there's any sane reason why this needs to be
 * constant time, given how slow erasure is.  But side channel attacks
 * can be tricky things, and it's theoretically possible that we could
 * leak information about, eg, key length, so we do constant time.
 */

static hal_error_t block_erase_maybe(const unsigned blockno)
{
  if (blockno >= NUM_FLASH_BLOCKS)
    return HAL_ERROR_IMPOSSIBLE;

  uint8_t mask = 0xFF;

  for (uint32_t a = block_offset(blockno); a < block_offset(blockno + 1); a += KEYSTORE_PAGE_SIZE) {
    uint8_t page[KEYSTORE_PAGE_SIZE];
    if (keystore_read_data(a, page, sizeof(page)) != 1)
      return HAL_ERROR_KEYSTORE_ACCESS;
    for (int i = 0; i < KEYSTORE_PAGE_SIZE; i++)
      mask &= page[i];
  }

  return mask == 0xFF ? HAL_OK : block_erase(blockno);
}

/*
 * Write a flash block, calculating CRC when appropriate.
 */

static hal_error_t block_write(const unsigned blockno, flash_block_t *block)
{
  if (block == NULL || blockno >= NUM_FLASH_BLOCKS || sizeof(*block) != KEYSTORE_SUBSECTOR_SIZE)
    return HAL_ERROR_IMPOSSIBLE;

  hal_error_t err = block_erase_maybe(blockno);

  if (err != HAL_OK)
    return err;

  switch (block_get_type(block)) {
  case BLOCK_TYPE_KEY:
  case BLOCK_TYPE_PIN:
  case BLOCK_TYPE_ATTR:
    block->header.crc = calculate_block_crc(block);
    break;
  default:
    break;
  }

  /* Sigh, magic numeric return codes */
  if (keystore_write_data(block_offset(blockno), block->bytes, sizeof(*block)) != 1)
    return HAL_ERROR_KEYSTORE_ACCESS;

  return HAL_OK;
}

/*
 * Update one flash block, including zombie jamboree.
 */

static hal_error_t block_update(const unsigned b1, flash_block_t *block,
                                const hal_uuid_t * const uuid, const unsigned chunk, int *hint)
{
  if (block == NULL)
    return HAL_ERROR_IMPOSSIBLE;

  if (db.ksi.used == db.ksi.size)
    return HAL_ERROR_NO_KEY_INDEX_SLOTS;

  cache_release(block);

  hal_error_t err;
  unsigned b2;

  if ((err = block_deprecate(b1))                                       != HAL_OK ||
      (err = hal_ks_index_replace(&db.ksi, uuid, chunk, &b2, hint))     != HAL_OK ||
      (err = block_write(b2, block))                                    != HAL_OK ||
      (err = block_zero(b1))                                            != HAL_OK)
    return err;

  cache_mark_used(block, b2);

  return block_erase_maybe(db.ksi.index[db.ksi.used]);
}

/*
 * Forward reference.
 */

static hal_error_t fetch_pin_block(unsigned *b, flash_block_t **block);

/*
 * Initialize keystore.  This includes various tricky bits, some of
 * which attempt to preserve the free list ordering across reboots, to
 * improve our simplistic attempt at wear leveling, others attempt to
 * recover from unclean shutdown.
 */

static inline void *gnaw(uint8_t **mem, size_t *len, const size_t size)
{
  if (mem == NULL || *mem == NULL || len == NULL || size > *len)
    return NULL;
  void *ret = *mem;
  *mem += size;
  *len -= size;
  return ret;
}

static hal_error_t ks_init(const hal_ks_driver_t * const driver)
{
  /*
   * Initialize the in-memory database.
   */

  size_t len = (sizeof(*db.ksi.index) * NUM_FLASH_BLOCKS +
                sizeof(*db.ksi.names) * NUM_FLASH_BLOCKS +
                sizeof(*db.cache)     * KS_FLASH_CACHE_SIZE);

  uint8_t *mem = hal_allocate_static_memory(len);

  if (mem == NULL)
    return HAL_ERROR_ALLOCATION_FAILURE;

  memset(&db, 0, sizeof(db));
  memset(mem, 0, len);

  db.ksi.index = gnaw(&mem, &len, sizeof(*db.ksi.index) * NUM_FLASH_BLOCKS);
  db.ksi.names = gnaw(&mem, &len, sizeof(*db.ksi.names) * NUM_FLASH_BLOCKS);
  db.cache     = gnaw(&mem, &len, sizeof(*db.cache)     * KS_FLASH_CACHE_SIZE);
  db.ksi.size  = NUM_FLASH_BLOCKS;
  db.ksi.used  = 0;

  if (db.ksi.index == NULL || db.ksi.names == NULL || db.cache == NULL)
    return HAL_ERROR_IMPOSSIBLE;

  for (int i = 0; i < KS_FLASH_CACHE_SIZE; i++)
    db.cache[i].blockno = ~0;

  /*
   * Scan existing content of flash to figure out what we've got.
   * This gets a bit involved due to the need to recover from things
   * like power failures at inconvenient times.
   */

  flash_block_type_t   block_types[NUM_FLASH_BLOCKS];
  flash_block_status_t block_status[NUM_FLASH_BLOCKS];
  flash_block_t *block = cache_pick_lru();
  int first_erased = -1;
  hal_error_t err;
  uint16_t n = 0;

  if (block == NULL)
    return HAL_ERROR_IMPOSSIBLE;

  for (int i = 0; i < NUM_FLASH_BLOCKS; i++) {

    /*
     * Read one block.  If the CRC is bad or the block type is
     * unknown, it's old data we don't understand, something we were
     * writing when we crashed, or bad flash; in any of these cases,
     * we want the block to ends up near the end of the free list.
     */

    err = block_read(i, block);

    if (err == HAL_ERROR_KEYSTORE_BAD_CRC || err == HAL_ERROR_KEYSTORE_BAD_BLOCK_TYPE)
      block_types[i] = BLOCK_TYPE_UNKNOWN;

    else if (err == HAL_OK)
      block_types[i] = block_get_type(block);

    else
      return err;

    switch (block_types[i]) {
    case BLOCK_TYPE_KEY:
    case BLOCK_TYPE_PIN:
    case BLOCK_TYPE_ATTR:
      block_status[i] = block_get_status(block);
      break;
    default:
      block_status[i] = BLOCK_STATUS_UNKNOWN;
    }

    /*
     * First erased block we see is head of the free list.
     */

    if (block_types[i] == BLOCK_TYPE_ERASED && first_erased < 0)
      first_erased = i;

    /*
     * If it's a valid data block, include it in the index.  We remove
     * tombstones (if any) below, for now it's easiest to include them
     * in the index, so we can look them up by name if we must.
     */

    const hal_uuid_t *uuid = NULL;

    switch (block_types[i]) {
    case BLOCK_TYPE_KEY:        uuid = &block->key.name;        break;
    case BLOCK_TYPE_ATTR:       uuid = &block->attr.name;       break;
    case BLOCK_TYPE_PIN:        uuid = &pin_uuid;               break;
    default:                    /* Keep GCC happy */            break;
    }

    if (uuid != NULL) {
      db.ksi.names[i].name = *uuid;
      db.ksi.names[i].chunk = block->header.this_chunk;
      db.ksi.index[n++] = i;
    }
  }

  db.ksi.used = n;

  assert(db.ksi.used <= db.ksi.size);

  /*
   * At this point we've built the (unsorted) index from all the valid
   * blocks.  Now we need to insert free and unrecognized blocks into
   * the free list in our preferred order.  It's possible that there's
   * a better way to do this than linear scan, but this is just
   * integer comparisons in a fairly small data set, so it's probably
   * not worth trying to optimize.
   */

  if (n < db.ksi.size)
    for (int i = 0; i < NUM_FLASH_BLOCKS; i++)
      if (block_types[i] == BLOCK_TYPE_ERASED)
        db.ksi.index[n++] = i;

  if (n < db.ksi.size)
    for (int i = first_erased; i < NUM_FLASH_BLOCKS; i++)
      if (block_types[i] == BLOCK_TYPE_ZEROED)
        db.ksi.index[n++] = i;

  if (n < db.ksi.size)
    for (int i = 0; i < first_erased; i++)
      if (block_types[i] == BLOCK_TYPE_ZEROED)
        db.ksi.index[n++] = i;

  if (n < db.ksi.size)
    for (int i = 0; i < NUM_FLASH_BLOCKS; i++)
      if (block_types[i] == BLOCK_TYPE_UNKNOWN)
        db.ksi.index[n++] = i;

  assert(n == db.ksi.size);

  /*
   * Initialize the index.
   */

  if ((err = hal_ks_index_setup(&db.ksi)) != HAL_OK)
    return err;

  /*
   * We might want to call hal_ks_index_fsck() here, if we can figure
   * out some safe set of recovery actions we can take.
   */

  /*
   * Deal with tombstones.  These are blocks left behind when
   * something bad (like a power failure) happened while we updating.
   * The sequence of operations while updating is designed so that,
   * barring a bug or a hardware failure, we should never lose data.
   *
   * For any tombstone we find, we start by looking for all the blocks
   * with a matching UUID, then see what valid sequences we can
   * construct from what we found.
   *
   * If we can construct a valid sequence of live blocks, the complete
   * update was written out, and we just need to zero the tombstones.
   *
   * Otherwise, if we can construct a complete sequence of tombstone
   * blocks, the update failed before it was completely written, so we
   * have to zero the incomplete sequence of live blocks then restore
   * from the tombstones.
   *
   * Otherwise, if the live and tombstone blocks taken together form a
   * valid sequence, the update failed while deprecating the old live
   * blocks, and the update itself was not written, so we need to
   * restore the tombstones and leave the live blocks alone.
   *
   * If none of the above applies, we don't understand what happened,
   * which is a symptom of either a bug or a hardware failure more
   * serious than simple loss of power or reboot at an inconvenient
   * time, so we error out to avoid accidental loss of data.
   */

  for (int i = 0; i < NUM_FLASH_BLOCKS; i++) {

    if (block_status[i] != BLOCK_STATUS_TOMBSTONE)
      continue;

    hal_uuid_t name = db.ksi.names[i].name;
    unsigned n_blocks;
    int where = -1;

    if ((err = hal_ks_index_find_range(&db.ksi, &name, 0, &n_blocks, NULL, &where)) != HAL_OK)
      return err;

    while (where > 0 && !hal_uuid_cmp(&name, &db.ksi.names[db.ksi.index[where - 1]].name)) {
      where--;
      n_blocks++;
    }

    int live_ok = 1, tomb_ok = 1, join_ok = 1;
    unsigned n_live = 0, n_tomb = 0;
    unsigned i_live = 0, i_tomb = 0;

    for (int j = 0; j < n_blocks; j++) {
      unsigned b = db.ksi.index[where + j];
      switch (block_status[b]) {
      case BLOCK_STATUS_LIVE:           n_live++;       break;
      case BLOCK_STATUS_TOMBSTONE:      n_tomb++;       break;
      default:                          return HAL_ERROR_IMPOSSIBLE;
      }
    }

    uint16_t live_blocks[n_live], tomb_blocks[n_tomb];

    for (int j = 0; j < n_blocks; j++) {
      unsigned b = db.ksi.index[where + j];

      if ((err = block_read(b, block)) != HAL_OK)
        return err;

      join_ok &= block->header.this_chunk == j && block->header.total_chunks == n_blocks;

      switch (block_status[b]) {
      case BLOCK_STATUS_LIVE:
        live_blocks[i_live] = b;
        live_ok &= block->header.this_chunk == i_live++ && block->header.total_chunks == n_live;
        break;
      case BLOCK_STATUS_TOMBSTONE:
        tomb_blocks[i_tomb] = b;
        tomb_ok &= block->header.this_chunk == i_tomb++ && block->header.total_chunks == n_tomb;
        break;
      default:
        return HAL_ERROR_IMPOSSIBLE;
      }
    }

    if (!live_ok && !tomb_ok && !join_ok)
      return HAL_ERROR_KEYSTORE_LOST_DATA;

    if (live_ok) {
      for (int j = 0; j < n_tomb; j++) {
        const unsigned b = tomb_blocks[j];
        if ((err = block_zero(b)) != HAL_OK)
          return err;
        block_types[b]  = BLOCK_TYPE_ZEROED;
        block_status[b] = BLOCK_STATUS_UNKNOWN;
      }
    }

    else if (tomb_ok) {
      for (int j = 0; j < n_live; j++) {
        const unsigned b = live_blocks[j];
        if ((err = block_zero(b)) != HAL_OK)
          return err;
        block_types[b]  = BLOCK_TYPE_ZEROED;
        block_status[b] = BLOCK_STATUS_UNKNOWN;
      }
    }

    if (live_ok) {
      memcpy(&db.ksi.index[where], live_blocks, n_live * sizeof(*db.ksi.index));
      memmove(&db.ksi.index[where + n_live], &db.ksi.index[where + n_blocks],
              (db.ksi.size - where - n_blocks) * sizeof(*db.ksi.index));
      memcpy(&db.ksi.index[db.ksi.size - n_tomb], tomb_blocks, n_tomb * sizeof(*db.ksi.index));
      db.ksi.used -= n_tomb;
      n_blocks = n_live;
    }

    else if (tomb_ok) {
      memcpy(&db.ksi.index[where], tomb_blocks, n_tomb * sizeof(*db.ksi.index));
      memmove(&db.ksi.index[where + n_tomb], &db.ksi.index[where + n_blocks],
              (db.ksi.size - where - n_blocks) * sizeof(*db.ksi.index));
      memcpy(&db.ksi.index[db.ksi.size - n_live], live_blocks, n_live * sizeof(*db.ksi.index));
      db.ksi.used -= n_live;
      n_blocks = n_tomb;
    }

    for (int j = 0; j < n_blocks; j++) {
      int hint = where + j;
      unsigned b1 = db.ksi.index[hint], b2;
      if (block_status[b1] != BLOCK_STATUS_TOMBSTONE)
        continue;
      if ((err = block_read(b1, block)) != HAL_OK)
        return err;
      block->header.block_status = BLOCK_STATUS_LIVE;
      if ((err = hal_ks_index_replace(&db.ksi, &name, j, &b2, &hint)) != HAL_OK ||
          (err = block_write(b2, block)) != HAL_OK)
        return err;
      block_types[b1]  = BLOCK_TYPE_ZEROED;
      block_status[b1] = BLOCK_STATUS_UNKNOWN;
      block_status[b2] = BLOCK_STATUS_LIVE;
    }
  }

  err = fetch_pin_block(NULL, &block);

  if (err == HAL_OK) {
    db.wheel_pin = block->pin.wheel_pin;
    db.so_pin    = block->pin.so_pin;
    db.user_pin  = block->pin.user_pin;
  }

  else if (err != HAL_ERROR_KEY_NOT_FOUND)
    return err;

  else {
    /*
     * We found no PIN block, so create one, with the user and so PINs
     * cleared and the wheel PIN set to the last-gasp value.  The
     * last-gasp WHEEL PIN is a terrible answer, but we need some kind
     * of bootstrapping mechanism when all else fails.  If you have a
     * better suggestion, we'd love to hear it.
     */

    unsigned b;

    memset(block, 0xFF, sizeof(*block));

    block->header.block_type   = BLOCK_TYPE_PIN;
    block->header.block_status = BLOCK_STATUS_LIVE;
    block->header.total_chunks = 1;
    block->header.this_chunk   = 0;

    block->pin.wheel_pin = db.wheel_pin = hal_last_gasp_pin;
    block->pin.so_pin    = db.so_pin;
    block->pin.user_pin  = db.user_pin;

    if ((err = hal_ks_index_add(&db.ksi, &pin_uuid, 0, &b, NULL)) != HAL_OK)
      return err;

    cache_mark_used(block, b);

    err = block_write(b, block);

    cache_release(block);

    if (err != HAL_OK)
      return err;
  }

  /*
   * Erase first block on free list if it's not already erased.
   */

  if (db.ksi.used < db.ksi.size &&
      (err = block_erase_maybe(db.ksi.index[db.ksi.used])) != HAL_OK)
    return err;

  /*
   * And we're finally done.
   */

  db.ks.driver = driver;

  return HAL_OK;
}

static hal_error_t ks_shutdown(const hal_ks_driver_t * const driver)
{
  if (db.ks.driver != driver)
    return HAL_ERROR_KEYSTORE_ACCESS;
  return HAL_OK;
}

static hal_error_t ks_open(const hal_ks_driver_t * const driver,
                                    hal_ks_t **ks)
{
  if (driver != hal_ks_token_driver || ks == NULL)
    return HAL_ERROR_BAD_ARGUMENTS;

  *ks = &db.ks;
  return HAL_OK;
}

static hal_error_t ks_close(hal_ks_t *ks)
{
  if (ks != NULL && ks != &db.ks)
    return HAL_ERROR_BAD_ARGUMENTS;

  return HAL_OK;
}

static inline int acceptable_key_type(const hal_key_type_t type)
{
  switch (type) {
  case HAL_KEY_TYPE_RSA_PRIVATE:
  case HAL_KEY_TYPE_EC_PRIVATE:
  case HAL_KEY_TYPE_RSA_PUBLIC:
  case HAL_KEY_TYPE_EC_PUBLIC:
    return 1;
  default:
    return 0;
  }
}

static hal_error_t ks_store(hal_ks_t *ks,
                            hal_pkey_slot_t *slot,
                            const uint8_t * const der, const size_t der_len)
{
  if (ks != &db.ks || slot == NULL || der == NULL || der_len == 0 || !acceptable_key_type(slot->type))
    return HAL_ERROR_BAD_ARGUMENTS;

  flash_block_t *block = cache_pick_lru();
  flash_key_block_t *k = &block->key;
  uint8_t kek[KEK_LENGTH];
  size_t kek_len;
  hal_error_t err;
  unsigned b;

  if (block == NULL)
    return HAL_ERROR_IMPOSSIBLE;

  if ((err = hal_ks_index_add(&db.ksi, &slot->name, 0, &b, &slot->hint)) != HAL_OK)
    return err;

  cache_mark_used(block, b);

  memset(block, 0xFF, sizeof(*block));

  block->header.block_type   = BLOCK_TYPE_KEY;
  block->header.block_status = BLOCK_STATUS_LIVE;
  block->header.total_chunks = 1;
  block->header.this_chunk   = 0;

  k->name    = slot->name;
  k->type    = slot->type;
  k->curve   = slot->curve;
  k->flags   = slot->flags;
  k->der_len = SIZEOF_FLASH_KEY_BLOCK_DER;
  k->attributes_len = 0;

  if ((err = hal_mkm_get_kek(kek, &kek_len, sizeof(kek))) == HAL_OK)
    err = hal_aes_keywrap(NULL, kek, kek_len, der, der_len, k->der, &k->der_len);

  memset(kek, 0, sizeof(kek));

  if (err == HAL_OK &&
      (err = block_write(b, block)) == HAL_OK)
    return HAL_OK;

  memset(block, 0, sizeof(*block));
  cache_release(block);
  (void) hal_ks_index_delete(&db.ksi, &slot->name, 0, NULL, &slot->hint);
  return err;
}

static hal_error_t ks_fetch(hal_ks_t *ks,
                            hal_pkey_slot_t *slot,
                            uint8_t *der, size_t *der_len, const size_t der_max)
{
  if (ks != &db.ks || slot == NULL)
    return HAL_ERROR_BAD_ARGUMENTS;

  flash_block_t *block;
  hal_error_t err;
  unsigned b;

  if ((err = hal_ks_index_find(&db.ksi, &slot->name, 0, &b, &slot->hint)) != HAL_OK ||
      (err = block_read_cached(b, &block))                                != HAL_OK)
    return err;

  if (block_get_type(block) != BLOCK_TYPE_KEY)
    return HAL_ERROR_KEYSTORE_WRONG_BLOCK_TYPE; /* HAL_ERROR_KEY_NOT_FOUND */

  cache_mark_used(block, b);

  flash_key_block_t *k = &block->key;

  slot->type  = k->type;
  slot->curve = k->curve;
  slot->flags = k->flags;

  if (der == NULL && der_len != NULL)
    *der_len = k->der_len;

  if (der != NULL) {

    uint8_t kek[KEK_LENGTH];
    size_t kek_len, der_len_;
    hal_error_t err;

    if (der_len == NULL)
      der_len = &der_len_;

    *der_len = der_max;

    if ((err = hal_mkm_get_kek(kek, &kek_len, sizeof(kek))) == HAL_OK)
      err = hal_aes_keyunwrap(NULL, kek, kek_len, k->der, k->der_len, der, der_len);

    memset(kek, 0, sizeof(kek));

    if (err != HAL_OK)
      return err;
  }

  return HAL_OK;
}

static hal_error_t ks_delete(hal_ks_t *ks,
                             hal_pkey_slot_t *slot)
{
  if (ks != &db.ks || slot == NULL)
    return HAL_ERROR_BAD_ARGUMENTS;

  hal_error_t err;
  unsigned n;

  if ((err = hal_ks_index_delete_range(&db.ksi, &slot->name, 0, &n, NULL, &slot->hint)) != HAL_OK)
    return err;

  unsigned b[n];

  if ((err = hal_ks_index_delete_range(&db.ksi, &slot->name, n, NULL, b, &slot->hint)) != HAL_OK)
    return err;

  for (int i = 0; i < n; i++)
    cache_release(cache_find_block(b[i]));

  for (int i = 0; i < n; i++)
    if ((err = block_zero(b[i])) != HAL_OK)
      return err;

  return block_erase_maybe(db.ksi.index[db.ksi.used]);
}

static hal_error_t ks_list(hal_ks_t *ks,
                           const hal_client_handle_t client,
                           const hal_session_handle_t session,
                           hal_pkey_info_t *result,
                           unsigned *result_len,
                           const unsigned result_max)
{
  if (ks != &db.ks || result == NULL || result_len == NULL)
    return HAL_ERROR_BAD_ARGUMENTS;

  flash_block_t *block;
  hal_error_t err;

  *result_len = 0;

  for (int i = 0; i < db.ksi.used; i++) {
    unsigned b = db.ksi.index[i];

    if (*result_len >= result_max)
      return HAL_ERROR_RESULT_TOO_LONG;

    if ((err = block_read_cached(b, &block)) != HAL_OK)
      return err;

    if (block_get_type(block) != BLOCK_TYPE_KEY || block->header.this_chunk > 0)
      continue;

    result[*result_len].type  = block->key.type;
    result[*result_len].curve = block->key.curve;
    result[*result_len].flags = block->key.flags;
    result[*result_len].name  = block->key.name;
    ++ *result_len;
  }

  return HAL_OK;
}

static inline hal_error_t locate_attributes(flash_block_t *block, const unsigned chunk,
                                            uint8_t **bytes, size_t *bytes_len,
                                            unsigned **attrs_len)
{
  if (block == NULL || bytes == NULL || bytes_len == NULL || attrs_len == NULL)
    return HAL_ERROR_IMPOSSIBLE;

  if (chunk == 0) {
    if (block_get_type(block) != BLOCK_TYPE_KEY)
      return HAL_ERROR_KEYSTORE_WRONG_BLOCK_TYPE; /* HAL_ERROR_KEY_NOT_FOUND */
    *attrs_len = &block->key.attributes_len;
    *bytes = block->key.der + block->key.der_len;
    *bytes_len = SIZEOF_FLASH_KEY_BLOCK_DER - block->key.der_len;
  }

  else {
    if (block_get_type(block) != BLOCK_TYPE_ATTR)
      return HAL_ERROR_KEYSTORE_WRONG_BLOCK_TYPE; /* HAL_ERROR_KEY_NOT_FOUND */
    *attrs_len = &block->attr.attributes_len;
    *bytes = block->attr.attributes;
    *bytes_len = SIZEOF_FLASH_ATTRIBUTE_BLOCK_ATTRIBUTES;
  }

  return HAL_OK;
}

static hal_error_t ks_match(hal_ks_t *ks,
                            const hal_client_handle_t client,
                            const hal_session_handle_t session,
                            const hal_key_type_t type,
                            const hal_curve_name_t curve,
                            const hal_key_flags_t flags,
                            const hal_rpc_pkey_attribute_t *attributes,
                            const unsigned attributes_len,
                            hal_uuid_t *result,
                            unsigned *result_len,
                            const unsigned result_max,
                            const hal_uuid_t * const previous_uuid)
{
  if (ks == NULL || attributes == NULL ||
      result == NULL || result_len == NULL || previous_uuid == NULL)
    return HAL_ERROR_BAD_ARGUMENTS;

  uint8_t need_attr[attributes_len > 0 ? attributes_len : 1];
  flash_block_t *block;
  int possible = 0;
  hal_error_t err;
  int i = -1;

  *result_len = 0;

  err = hal_ks_index_find(&db.ksi, previous_uuid, 0, NULL, &i);

  if (err == HAL_ERROR_KEY_NOT_FOUND)
    i--;
  else if (err != HAL_OK)
    return err;

  while (*result_len < result_max && ++i < db.ksi.used) {

    unsigned b = db.ksi.index[i];

    if (db.ksi.names[b].chunk == 0)
      possible = 1;

    if (!possible)
      continue;

    if ((err = block_read_cached(b, &block)) != HAL_OK)
      return err;

    if (db.ksi.names[b].chunk == 0) {
      memset(need_attr, 1, sizeof(need_attr));
      possible = ((type == HAL_KEY_TYPE_NONE || type  == block->key.type) &&
                  (curve == HAL_CURVE_NONE   || curve == block->key.curve));
    }

    if (!possible)
      continue;

    if (attributes_len > 0) {
      uint8_t *bytes = NULL;
      size_t bytes_len = 0;
      unsigned *attrs_len;

      if ((err = locate_attributes(block, db.ksi.names[b].chunk,
                                   &bytes, &bytes_len, &attrs_len)) != HAL_OK)
        return err;

      if (*attrs_len > 0) {
        hal_rpc_pkey_attribute_t attrs[*attrs_len];

        if ((err = hal_ks_attribute_scan(bytes, bytes_len, attrs, *attrs_len, NULL)) != HAL_OK)
          return err;

        for (int j = 0; possible && j < attributes_len; j++) {

          if (!need_attr[j])
            continue;

          for (hal_rpc_pkey_attribute_t *a = attrs; a < attrs + *attrs_len; a++) {
            if (a->type != attributes[j].type)
              continue;
            need_attr[j] = 0;
            possible = (a->length == attributes[j].length &&
                        !memcmp(a->value, attributes[j].value, a->length));
            break;
          }
        }
      }
    }

    if (!possible)
      continue;

    if (attributes_len > 0 && memchr(need_attr, 1, sizeof(need_attr)) != NULL)
      continue;

    result[*result_len] = db.ksi.names[b].name;
    ++*result_len;
    possible = 0;
  }

  return HAL_OK;
}

static  hal_error_t ks_set_attribute(hal_ks_t *ks,
                                     hal_pkey_slot_t *slot,
                                     const uint32_t type,
                                     const uint8_t * const value,
                                     const size_t value_len)
{
  if (ks != &db.ks || slot == NULL)
    return HAL_ERROR_BAD_ARGUMENTS;

  /*
   * Try to add new attribute as a single-block update.
   */

  flash_block_t *block;
  unsigned chunk = 0;
  hal_error_t err;

  do {
    int hint = slot->hint + chunk;
    unsigned b;

    if ((err = hal_ks_index_find(&db.ksi, &slot->name, chunk, &b, &hint)) != HAL_OK ||
        (err = block_read_cached(b, &block))                              != HAL_OK)
      return err;

    if (block->header.this_chunk != chunk)
      return HAL_ERROR_IMPOSSIBLE;

    if (chunk == 0)
      slot->hint = hint;

    uint8_t *bytes = NULL;
    size_t bytes_len = 0;
    unsigned *attrs_len;

    if ((err = locate_attributes(block, chunk, &bytes, &bytes_len, &attrs_len)) != HAL_OK)
      return err;

    cache_mark_used(block, b);

    hal_rpc_pkey_attribute_t attrs[*attrs_len + 1];
    const unsigned old_attrs_len = *attrs_len;
    size_t total;

    if ((err = hal_ks_attribute_scan(bytes, bytes_len, attrs, *attrs_len, &total)) != HAL_OK)
      return err;

    err = hal_ks_attribute_insert(bytes, bytes_len, attrs, attrs_len, &total, type, value, value_len);

    if (*attrs_len != old_attrs_len && err != HAL_OK)
      cache_release(block);

    if (err == HAL_ERROR_RESULT_TOO_LONG)
      continue;

    if (err != HAL_OK)
      return err;

    return block_update(b, block, &slot->name, chunk, &hint);

  } while (++chunk < block->header.total_chunks);

  /*
   * If we get here, we have to add a new block, which requires
   * rewriting all the others to bump the total_blocks count.  We need
   * to keep track of all the old chunks so we can zero them at the
   * end, and because we can't zero them until we've written out the
   * new chunks, we need enough free blocks for the entire new object.
   */

  const unsigned total_chunks = block->header.total_chunks;
  unsigned b, blocks[total_chunks];

  if (db.ksi.used + total_chunks + 1 > db.ksi.size)
    return HAL_ERROR_NO_KEY_INDEX_SLOTS;

  /*
   * Phase 1: Deprecate all the old chunks, remember where the were.
   */

  for (chunk = 0; chunk < total_chunks; chunk++) {
    int hint = slot->hint + chunk;
    if ((err = hal_ks_index_find(&db.ksi, &slot->name, chunk, &blocks[chunk], &hint)) != HAL_OK ||
        (err = block_deprecate(blocks[chunk]))                                        != HAL_OK)
      return err;
  }

  /*
   * Phase 2: Rewrite all the existing chunks with the new total_chunks value.
   */

  for (chunk = 0; chunk < total_chunks; chunk++) {
    int hint = slot->hint + chunk;
    if ((err = block_read_cached(blocks[chunk], &block)) != HAL_OK)
      return err;
    if (block->header.this_chunk != chunk)
      return HAL_ERROR_IMPOSSIBLE;
    block->header.block_status = BLOCK_STATUS_LIVE;
    block->header.total_chunks = total_chunks + 1;

    uint8_t *bytes = NULL;
    size_t bytes_len = 0;
    unsigned *attrs_len;
    size_t total;

    if ((err = locate_attributes(block, chunk, &bytes, &bytes_len, &attrs_len)) != HAL_OK)
      return err;

    if (*attrs_len > 0) {
      hal_rpc_pkey_attribute_t attrs[*attrs_len];
      if ((err = hal_ks_attribute_scan(bytes, bytes_len, attrs, *attrs_len, &total)) != HAL_OK ||
          (err = hal_ks_attribute_delete(bytes, bytes_len, attrs, attrs_len, &total, type)) != HAL_OK)
        return err;
    }

    unsigned b;

    if ((err = hal_ks_index_replace(&db.ksi, &slot->name, chunk, &b, &hint))    != HAL_OK ||
        (err = block_write(b, block))                                           != HAL_OK)
      return err;
  }

  /*
   * Phase 3: Write the new chunk.
   */

  {
    block = cache_pick_lru();

    memset(block, 0xFF, sizeof(*block));

    block->header.block_type   = BLOCK_TYPE_ATTR;
    block->header.block_status = BLOCK_STATUS_LIVE;
    block->header.total_chunks = total_chunks + 1;
    block->header.this_chunk   = total_chunks;
    block->attr.name = slot->name;
    block->attr.attributes_len = 0;

    hal_rpc_pkey_attribute_t attrs[1];
    size_t total = 0;

    if ((err = hal_ks_attribute_insert(block->attr.attributes,
                                       SIZEOF_FLASH_ATTRIBUTE_BLOCK_ATTRIBUTES,
                                       attrs, &block->attr.attributes_len, &total,
                                       type, value, value_len))                         != HAL_OK ||
        (err = hal_ks_index_add(&db.ksi, &slot->name, total_chunks, &b, NULL))          != HAL_OK ||
        (err = block_write(b, block))                                                   != HAL_OK)
      return err;

    cache_mark_used(block, b);
  }

  /*
   * Phase 4: Zero the old chunks we deprecated in phase 1.
   */

  for (chunk = 0; chunk < total_chunks; chunk++)
    if ((err = block_zero(blocks[chunk])) != HAL_OK)
      return err;

  return HAL_OK;
}

static  hal_error_t ks_get_attribute(hal_ks_t *ks,
                                     hal_pkey_slot_t *slot,
                                     const uint32_t type,
                                     uint8_t *value,
                                     size_t *value_len,
                                     const size_t value_max)
{
  if (ks != &db.ks || slot == NULL)
    return HAL_ERROR_BAD_ARGUMENTS;

  flash_block_t *block;
  hal_error_t err;
  unsigned b;

  hal_rpc_pkey_attribute_t a = {0, 0, NULL};
  unsigned chunk = 0;

  do {
    int hint = slot->hint + chunk;

    if ((err = hal_ks_index_find(&db.ksi, &slot->name, chunk, &b, &hint)) != HAL_OK ||
        (err = block_read_cached(b, &block))                              != HAL_OK)
      return err;

    if (block->header.this_chunk != chunk)
      return HAL_ERROR_IMPOSSIBLE;

    if (chunk == 0)
      slot->hint = hint;

    cache_mark_used(block, b);

    uint8_t *bytes = NULL;
    size_t bytes_len = 0;
    unsigned *attrs_len;

    if ((err = locate_attributes(block, chunk, &bytes, &bytes_len, &attrs_len)) != HAL_OK)
      return err;

    if (*attrs_len == 0)
      continue;

    hal_rpc_pkey_attribute_t attrs[*attrs_len];

    if ((err = hal_ks_attribute_scan(bytes, bytes_len, attrs, *attrs_len, NULL)) != HAL_OK)
      return err;

    for (int i = 0; a.value == NULL && i < *attrs_len; ++i)
      if (attrs[i].type == type)
        a = attrs[i];

  } while (a.value == NULL && ++chunk < block->header.total_chunks);

  if (a.value == NULL)
    return HAL_ERROR_ATTRIBUTE_NOT_FOUND;

  if (a.length > value_max && value != NULL)
    return HAL_ERROR_RESULT_TOO_LONG;

  if (value != NULL)
    memcpy(value, a.value, a.length);

  if (value_len != NULL)
    *value_len = a.length;

  return HAL_OK;
}

static hal_error_t ks_delete_attribute(hal_ks_t *ks,
                                       hal_pkey_slot_t *slot,
                                       const uint32_t type)
{
  /*
   * For extra credit, we could handle attribute compaction here, but
   * in practice we expect attribute deletion without deleting the
   * entire object to be a rare enough event that it may not be worth
   * it.  Certainly it's not a high priority, so later, if ever.
   */

  if (ks != &db.ks || slot == NULL)
    return HAL_ERROR_BAD_ARGUMENTS;

  flash_block_t *block;
  unsigned chunk = 0;

  do {
    int hint = slot->hint + chunk;
    hal_error_t err;
    unsigned b;

    if ((err = hal_ks_index_find(&db.ksi, &slot->name, chunk, &b, &hint)) != HAL_OK ||
        (err = block_read_cached(b, &block))                              != HAL_OK)
      return err;

    if (block->header.this_chunk != chunk)
      return HAL_ERROR_IMPOSSIBLE;

    if (chunk == 0)
      slot->hint = hint;

    uint8_t *bytes = NULL;
    size_t bytes_len = 0;
    unsigned *attrs_len;

    if ((err = locate_attributes(block, chunk, &bytes, &bytes_len, &attrs_len)) != HAL_OK)
      return err;

    cache_mark_used(block, b);

    if (*attrs_len == 0)
      continue;

    hal_rpc_pkey_attribute_t attrs[*attrs_len];
    const unsigned old_attrs_len = *attrs_len;
    size_t total;

    if ((err = hal_ks_attribute_scan(  bytes, bytes_len, attrs, *attrs_len, &total))       != HAL_OK ||
        (err = hal_ks_attribute_delete(bytes, bytes_len, attrs,  attrs_len, &total, type)) != HAL_OK)
      return err;

    if (*attrs_len == old_attrs_len)
      continue;

    if ((err = block_update(b, block, &slot->name, chunk, &hint)) != HAL_OK)
      return err;

  } while (++chunk < block->header.total_chunks);

  return HAL_OK;
}

static  hal_error_t ks_set_attributes(hal_ks_t *ks,
                                      hal_pkey_slot_t *slot,
                                      const hal_rpc_pkey_attribute_t *attributes,
                                      const unsigned attributes_len)
{
#warning This function is much too long
  // Probably needs to be broken up into multiple sub-functions, or at least
  // into discrete blocks to scope most of the variables, but let's finish
  // writing the icky version before polishing the chrome.

  if (ks != &db.ks || slot == NULL || attributes == NULL || attributes_len == 0)
    return HAL_ERROR_BAD_ARGUMENTS;

  /*
   * Try to add new attribute as a single-block update.
   */

  unsigned updated_attributes_len = attributes_len;
  flash_block_t *block;
  unsigned chunk = 0;
  hal_error_t err;
  unsigned b;

  do {
    int hint = slot->hint + chunk;

    if ((err = hal_ks_index_find(&db.ksi, &slot->name, chunk, &b, &hint)) != HAL_OK ||
        (err = block_read_cached(b, &block))                              != HAL_OK)
      return err;

    if (block->header.this_chunk != chunk)
      return HAL_ERROR_IMPOSSIBLE;

    cache_mark_used(block, b);

    if (chunk == 0)
      slot->hint = hint;

    uint8_t *bytes = NULL;
    size_t bytes_len = 0;
    unsigned *attrs_len;

    if ((err = locate_attributes(block, chunk, &bytes, &bytes_len, &attrs_len)) != HAL_OK)
      return err;

    updated_attributes_len += *attrs_len;

    hal_rpc_pkey_attribute_t attrs[*attrs_len + attributes_len];
    size_t total;

    if ((err = hal_ks_attribute_scan(bytes, bytes_len, attrs, *attrs_len, &total)) != HAL_OK)
      return err;

    for (int i = 0; err == HAL_OK && i < attributes_len; i++) {
      if (attributes[i].length == 0)
        err = hal_ks_attribute_delete(bytes, bytes_len, attrs, attrs_len, &total,
                                      attributes[i].type);
      else
        err = hal_ks_attribute_insert(bytes, bytes_len, attrs, attrs_len, &total,
                                      attributes[i].type,
                                      attributes[i].value,
                                      attributes[i].length);
      if (err != HAL_OK)
        cache_release(block);
    }

    if (err == HAL_ERROR_RESULT_TOO_LONG)
      continue;

    if (err != HAL_OK)
      return err;

    return block_update(b, block, &slot->name, chunk, &hint);

  } while (++chunk < block->header.total_chunks);

  /*
   * If we get here, we have to add a new block, which requires
   * rewriting all the others to bump the total_blocks count.  We need
   * to keep track of all the old chunks so we can zero them at the
   * end, and because we can't zero them until we've written out the
   * new chunks, we need enough free blocks for the entire new object.
   *
   * Calculating all of this is extremely tedious, but flash writes
   * are so much more expensive than anything else we do here that
   * it's almost certainly worth it.
   *
   * We don't need the attribute values to compute the sizes, just the
   * attribute sizes, so we scan all the existing blocks, build up a
   * structure with the current attribute types and sizes, modify that
   * according to our arguments, and compute the needed size.  Once we
   * have that, we can start rewriting existing blocks.  We put all
   * the new stuff at the end, which simplifies this slightly.
   *
   * In theory, this process never requires us to have more than two
   * blocks in memory at the same time (source and destination when
   * copying across chunk boundaries), but having enough cache buffers
   * to keep the whole set in memory will almost certainly make this
   * run faster.
   */

  hal_rpc_pkey_attribute_t updated_attributes[updated_attributes_len];
  const unsigned total_chunks_old = block->header.total_chunks;
  size_t bytes_available = 0;

  updated_attributes_len = 0;

  for (chunk = 0; chunk < total_chunks_old; chunk++) {
    int hint = slot->hint + chunk;

    if ((err = hal_ks_index_find(&db.ksi, &slot->name, chunk, &b, &hint)) != HAL_OK ||
        (err = block_read_cached(b, &block))                              != HAL_OK)
      return err;

    if (block->header.this_chunk != chunk)
      return HAL_ERROR_IMPOSSIBLE;

    cache_mark_used(block, b);

    uint8_t *bytes = NULL;
    size_t bytes_len = 0;
    unsigned *attrs_len;

    if ((err = locate_attributes(block, chunk, &bytes, &bytes_len, &attrs_len)) != HAL_OK)
      return err;

    hal_rpc_pkey_attribute_t attrs[*attrs_len];
    size_t total;

    if ((err = hal_ks_attribute_scan(bytes, bytes_len, attrs, *attrs_len, &total)) != HAL_OK)
      return err;

    if (chunk == 0)
      bytes_available = bytes_len;

    for (int i = 0; i < *attrs_len; i++) {
      if (updated_attributes_len >= sizeof(updated_attributes)/sizeof(*updated_attributes))
        return HAL_ERROR_IMPOSSIBLE;
      updated_attributes[updated_attributes_len].type = attrs[i].type;
      updated_attributes[updated_attributes_len].length = attrs[i].length;
      updated_attributes[updated_attributes_len].value = NULL;
      updated_attributes_len++;
    }
  }

  for (int i = 0; i < attributes_len; i++) {

    for (int j = 0; j < updated_attributes_len; j++)
      if (updated_attributes[j].type == attributes[i].type)
        updated_attributes[j].length = 0;

    if (updated_attributes_len >= sizeof(updated_attributes)/sizeof(*updated_attributes))
      return HAL_ERROR_IMPOSSIBLE;
    updated_attributes[updated_attributes_len].type   = attributes[i].type;
    updated_attributes[updated_attributes_len].length = attributes[i].length;
    updated_attributes[updated_attributes_len].value  = attributes[i].value;
    updated_attributes_len++;
  }

  chunk = 0;

  for (int i = 0; i < updated_attributes_len; i++) {

    if (updated_attributes[i].length == 0) {
      memmove(&updated_attributes[i], &updated_attributes[i + 1], updated_attributes_len - i - 1);
      updated_attributes_len--;
      i--;
      continue;
    }

    const size_t needed = hal_ks_attribute_header_size + updated_attributes[i].length;

    if (needed > bytes_available) {
      bytes_available = SIZEOF_FLASH_ATTRIBUTE_BLOCK_ATTRIBUTES;
      chunk++;
    }

    if (needed > bytes_available)
      return HAL_ERROR_RESULT_TOO_LONG;

    bytes_available -= needed;
  }

  const unsigned total_chunks_new = chunk + 1;

  if (db.ksi.used + total_chunks_new > db.ksi.size)
    return HAL_ERROR_NO_KEY_INDEX_SLOTS;

  /*
   * Phase 1: Deprecate all the old chunks, remember where they were.
   */

  unsigned old_blocks[total_chunks_old];

  for (chunk = 0; chunk < total_chunks_old; chunk++) {
    int hint = slot->hint + chunk;
    if ((err = hal_ks_index_find(&db.ksi, &slot->name, chunk, &b, &hint)) != HAL_OK ||
        (err = block_deprecate(b))                                        != HAL_OK)
      return err;
    old_blocks[chunk] = b;
  }

  /*
   * Phase 2: Write new chunks, copying attributes from old chunks and attributes[]
   * as needed.  This is tedious.
   */

  {
    hal_rpc_pkey_attribute_t old_attrs[updated_attributes_len], new_attrs[updated_attributes_len];
    unsigned                *old_attrs_len = NULL,             *new_attrs_len = NULL;
    flash_block_t           *old_block     = NULL,             *new_block     = NULL;
    uint8_t                 *old_bytes     = NULL,             *new_bytes     = NULL;
    size_t                   old_bytes_len = 0,                 new_bytes_len = 0;
    unsigned                 old_chunk     = 0,                 new_chunk     = 0;
    size_t                   old_total     = 0,                 new_total     = 0;

    int updated_attributes_i = 0, old_attrs_i = 0;

    uint32_t       new_attr_type;
    size_t         new_attr_length;
    const uint8_t *new_attr_value;

    while (updated_attributes_i < updated_attributes_len) {

      if (old_chunk >= total_chunks_old || new_chunk >= total_chunks_new)
        return HAL_ERROR_IMPOSSIBLE;

      if (updated_attributes[updated_attributes_i].value != NULL) {
        new_attr_type   = updated_attributes[updated_attributes_i].type;
        new_attr_length = updated_attributes[updated_attributes_i].length;
        new_attr_value  = updated_attributes[updated_attributes_i].value;
      }

      else {

        if (old_block == NULL) {

          if ((err = block_read_cached(old_blocks[old_chunk], &old_block)) != HAL_OK)
            return err;

          if (old_block->header.this_chunk != old_chunk)
            return HAL_ERROR_IMPOSSIBLE;

          if ((err = locate_attributes(old_block, old_chunk,
                                       &old_bytes, &old_bytes_len, &old_attrs_len)) != HAL_OK ||
              (err = hal_ks_attribute_scan(old_bytes, old_bytes_len,
                                           old_attrs, *old_attrs_len, &old_total))  != HAL_OK)
            return err;

          old_attrs_i = 0;
        }

        while (old_attrs_i < *old_attrs_len &&
               old_attrs[old_attrs_i].type != updated_attributes[updated_attributes_i].type)
          old_attrs_i++;

        if (old_attrs_i >= *old_attrs_len) {
          old_chunk++;
          old_block = NULL;
          continue;
        }

        new_attr_type   = old_attrs[old_attrs_i].type;
        new_attr_length = old_attrs[old_attrs_i].length;
        new_attr_value  = old_attrs[old_attrs_i].value;
      }

      if (new_block == NULL) {

        new_block = cache_pick_lru();
        memset(new_block, 0xFF, sizeof(*new_block));

        if (new_chunk == 0) {
          flash_block_t *tmp_block;
          if ((err = block_read_cached(old_blocks[0], &tmp_block)) != HAL_OK)
            return err;
          if (tmp_block->header.this_chunk != 0)
            return HAL_ERROR_IMPOSSIBLE;
          new_block->header.block_type   = BLOCK_TYPE_KEY;
          new_block->key.name            = slot->name;
          new_block->key.type            = tmp_block->key.type;
          new_block->key.curve           = tmp_block->key.curve;
          new_block->key.flags           = tmp_block->key.flags;
          new_block->key.der_len         = tmp_block->key.der_len;
          new_block->key.attributes_len  = 0;
          memcpy(new_block->key.der, tmp_block->key.der, tmp_block->key.der_len);
        }
        else {
          new_block->header.block_type   = BLOCK_TYPE_ATTR;
          new_block->attr.name           = slot->name;
          new_block->attr.attributes_len = 0;
        }

        new_block->header.block_status = BLOCK_STATUS_LIVE;
        new_block->header.total_chunks = total_chunks_new;
        new_block->header.this_chunk   = new_chunk;

        if ((err = locate_attributes(new_block, new_chunk,
                                     &new_bytes, &new_bytes_len, &new_attrs_len)) != HAL_OK)
          return err;

        new_total = 0;
      }

      err = hal_ks_attribute_insert(new_bytes, new_bytes_len, new_attrs, new_attrs_len, &new_total,
                                    new_attr_type, new_attr_value, new_attr_length);

      switch (err) {
      case HAL_OK:
        if (++updated_attributes_i >= updated_attributes_len)
          continue;
        break;
      case HAL_ERROR_RESULT_TOO_LONG:
        if (new_chunk == 0 || new_attrs_len > 0)
          break;
      default:
        return err;
      }

      int hint = slot->hint + new_chunk;

      if (new_chunk < total_chunks_old)
        err = hal_ks_index_replace(&db.ksi, &slot->name, new_chunk, &b, &hint);
      else
        err = hal_ks_index_add(    &db.ksi, &slot->name, new_chunk, &b, &hint);

      if (err != HAL_OK || (err = block_write(b, new_block)) != HAL_OK)
        return err;

      cache_mark_used(new_block, b);

      new_block = NULL;
      new_chunk++;
    }
  }

  /*
   * Phase 3: Zero the old chunks we deprecated in phase 1.
   */

  for (chunk = 0; chunk < total_chunks_old; chunk++)
    if ((err = block_zero(old_blocks[chunk])) != HAL_OK)
      return err;

  return HAL_OK;
}

static  hal_error_t ks_get_attributes(hal_ks_t *ks,
                                      hal_pkey_slot_t *slot,
                                      hal_rpc_pkey_attribute_t *attributes,
                                      const unsigned attributes_len,
                                      uint8_t *attributes_buffer,
                                      const size_t attributes_buffer_len)
{
  if (ks != &db.ks || slot == NULL || attributes == NULL || attributes_len == 0 ||
      attributes_buffer == NULL || attributes_buffer_len == 0)
    return HAL_ERROR_BAD_ARGUMENTS;

  for (int i = 0; i < attributes_len; i++) {
    attributes[i].length = 0;
    attributes[i].value  = NULL;
  }

  uint8_t *abuf = attributes_buffer;
  flash_block_t *block = NULL;
  unsigned chunk = 0;
  unsigned found = 0;
  hal_error_t err;
  unsigned b;

  do {
    int hint = slot->hint + chunk;

    if ((err = hal_ks_index_find(&db.ksi, &slot->name, chunk, &b, &hint)) != HAL_OK ||
        (err = block_read_cached(b, &block))                              != HAL_OK)
      return err;

    if (block->header.this_chunk != chunk)
      return HAL_ERROR_IMPOSSIBLE;

    if (chunk == 0)
      slot->hint = hint;

    cache_mark_used(block, b);

    uint8_t *bytes = NULL;
    size_t bytes_len = 0;
    unsigned *attrs_len;

    if ((err = locate_attributes(block, chunk, &bytes, &bytes_len, &attrs_len)) != HAL_OK)
      return err;

    if (*attrs_len == 0)
      continue;

    hal_rpc_pkey_attribute_t attrs[*attrs_len];

    if ((err = hal_ks_attribute_scan(bytes, bytes_len, attrs, *attrs_len, NULL)) != HAL_OK)
      return err;

    for (int i = 0; i < attributes_len; i++) {

      if (attributes[i].value != NULL)
        continue;

      int j = 0;
      while (j < *attrs_len && attrs[j].type != attributes[i].type)
        j++;
      if (j >= *attrs_len)
        continue;

      if (attrs[j].length > attributes_buffer + attributes_buffer_len - abuf)
        return HAL_ERROR_RESULT_TOO_LONG;

      memcpy(abuf, attrs[j].value, attrs[j].length);
      attributes[i].value  = abuf;
      attributes[i].length = attrs[j].length;
      abuf += attrs[j].length;
      found++;
    }

  } while (found < attributes_len && ++chunk < block->header.total_chunks);

  if (found < attributes_len)
    return HAL_ERROR_ATTRIBUTE_NOT_FOUND;

  return HAL_OK;
}

static hal_error_t ks_delete_attributes(hal_ks_t *ks,
                                        hal_pkey_slot_t *slot,
                                        const uint32_t *types,
                                        const unsigned types_len)
{
  // Most likely we will remove this function from the API entirely,
  // but for now implement it in terms of ks_set_attributes() to keep
  // all the horrid update logic in one place.

  if (ks != &db.ks || slot == NULL || types == NULL || types_len == 0)
    return HAL_ERROR_BAD_ARGUMENTS;

  hal_rpc_pkey_attribute_t attributes[types_len];

  for (int i = 0; i < types_len; i++) {
    attributes[i].type   = types[i];
    attributes[i].length = 0;
    attributes[i].value  = NULL;
  }

  return ks_set_attributes(ks, slot, attributes, types_len);
}

const hal_ks_driver_t hal_ks_token_driver[1] = {{
  ks_init,
  ks_shutdown,
  ks_open,
  ks_close,
  ks_store,
  ks_fetch,
  ks_delete,
  ks_list,
  ks_match,
  ks_set_attribute,
  ks_get_attribute,
  ks_delete_attribute,
  ks_set_attributes,
  ks_get_attributes,
  ks_delete_attributes
}};

/*
 * The remaining functions aren't really part of the keystore API per se,
 * but they all involve non-key data which we keep in the keystore
 * because it's the flash we've got.
 */

/*
 * Fetch PIN.  This is always cached, so just returned cached value.
 */

hal_error_t hal_get_pin(const hal_user_t user,
                        const hal_ks_pin_t **pin)
{
  if (pin == NULL)
    return HAL_ERROR_BAD_ARGUMENTS;

  switch (user) {
  case HAL_USER_WHEEL:  *pin = &db.wheel_pin;  break;
  case HAL_USER_SO:     *pin = &db.so_pin;     break;
  case HAL_USER_NORMAL: *pin = &db.user_pin;   break;
  default:              return HAL_ERROR_BAD_ARGUMENTS;
  }

  return HAL_OK;
}

/*
 * Fetch PIN block.  hint = 0 because we know that the all-zeros UUID
 * should always sort to first slot in the index.
 */

static hal_error_t fetch_pin_block(unsigned *b, flash_block_t **block)
{
  if (block == NULL)
    return HAL_ERROR_IMPOSSIBLE;

  hal_error_t err;
  int hint = 0;
  unsigned b_;

  if (b == NULL)
    b = &b_;

  if ((err = hal_ks_index_find(&db.ksi, &pin_uuid, 0, b, &hint)) != HAL_OK ||
      (err = block_read_cached(*b, block))                       != HAL_OK)
    return err;

  cache_mark_used(*block, *b);

  if (block_get_type(*block) != BLOCK_TYPE_PIN)
    return HAL_ERROR_IMPOSSIBLE;

  return HAL_OK;
}

/*
 * Update the PIN block.  This block should always be present, but we
 * have to do the zombie jamboree to make sure we write the new PIN
 * block before destroying the old one.  hint = 0 because we know that
 * the all-zeros UUID should always sort to first slot in the index.
 */

static hal_error_t update_pin_block(const unsigned b,
                                    flash_block_t *block,
                                    const flash_pin_block_t * const new_data)
{
  if (block == NULL || new_data == NULL || block_get_type(block) != BLOCK_TYPE_PIN)
    return HAL_ERROR_IMPOSSIBLE;

  int hint = 0;

  block->pin = *new_data;

  return block_update(b, block, &pin_uuid, 0, &hint);
}

/*
 * Change a PIN.
 */

hal_error_t hal_set_pin(const hal_user_t user,
                        const hal_ks_pin_t * const pin)
{
  if (pin == NULL)
    return HAL_ERROR_BAD_ARGUMENTS;

  flash_block_t *block;
  hal_error_t err;
  unsigned b;

  if ((err = fetch_pin_block(&b, &block)) != HAL_OK)
    return err;

  flash_pin_block_t new_data = block->pin;
  hal_ks_pin_t *dp, *bp;

  switch (user) {
  case HAL_USER_WHEEL:  bp = &new_data.wheel_pin; dp = &db.wheel_pin; break;
  case HAL_USER_SO:     bp = &new_data.so_pin;    dp = &db.so_pin;    break;
  case HAL_USER_NORMAL: bp = &new_data.user_pin;  dp = &db.user_pin;  break;
  default:              return HAL_ERROR_BAD_ARGUMENTS;
  }

  const hal_ks_pin_t old_pin = *dp;
  *dp = *bp = *pin;

  if ((err = update_pin_block(b, block, &new_data)) != HAL_OK)
    *dp = old_pin;

  return err;
}

#if HAL_MKM_FLASH_BACKUP_KLUDGE

/*
 * Horrible insecure kludge in lieu of a battery for the MKM.
 *
 * API here is a little strange: all calls pass a length parameter,
 * but any length other than the compiled in constant just returns an
 * immediate error, there's no notion of buffer max length vs buffer
 * used length, querying for the size of buffer really needed, or
 * anything like that.
 *
 * We might want to rewrite this some day, if we don't replace it with
 * a battery first.  For now we just preserve the API as we found it
 * while re-implementing it on top of the new keystore.
 */

hal_error_t hal_mkm_flash_read(uint8_t *buf, const size_t len)
{
  if (buf != NULL && len != KEK_LENGTH)
    return HAL_ERROR_MASTERKEY_BAD_LENGTH;

  flash_block_t *block;
  hal_error_t err;
  unsigned b;

  if ((err = fetch_pin_block(&b, &block)) != HAL_OK)
    return err;

  if (block->pin.kek_set != FLASH_KEK_SET)
    return HAL_ERROR_MASTERKEY_NOT_SET;

  if (buf != NULL)
    memcpy(buf, block->pin.kek, len);

  return HAL_OK;
}

hal_error_t hal_mkm_flash_write(const uint8_t * const buf, const size_t len)
{
  if (buf == NULL)
    return HAL_ERROR_BAD_ARGUMENTS;

  if (len != KEK_LENGTH)
    return HAL_ERROR_MASTERKEY_BAD_LENGTH;

  flash_block_t *block;
  hal_error_t err;
  unsigned b;

  if ((err = fetch_pin_block(&b, &block)) != HAL_OK)
    return err;

  flash_pin_block_t new_data = block->pin;

  new_data.kek_set = FLASH_KEK_SET;
  memcpy(new_data.kek, buf, len);

  return update_pin_block(b, block, &new_data);
}

hal_error_t hal_mkm_flash_erase(const size_t len)
{
  if (len != KEK_LENGTH)
    return HAL_ERROR_MASTERKEY_BAD_LENGTH;

  flash_block_t *block;
  hal_error_t err;
  unsigned b;

  if ((err = fetch_pin_block(&b, &block)) != HAL_OK)
    return err;

  flash_pin_block_t new_data = block->pin;

  new_data.kek_set = FLASH_KEK_SET;
  memset(new_data.kek, 0, len);

  return update_pin_block(b, block, &new_data);
}

#endif /* HAL_MKM_FLASH_BACKUP_KLUDGE */


/*
 * Local variables:
 * indent-tabs-mode: nil
 * End:
 */