aboutsummaryrefslogblamecommitdiff
path: root/ks_flash.c
blob: 957ded3acb6d9b09597be088b1795cc8ad96e952 (plain) (tree)
1
2
3
4
5
6
7
1253
1254
1255
1256
1257
1258
1259
1260
1261
1262
1263
1264
1265
1266
1267
1268
1269
1270
1271
1272
1273
1274
1275
1276
1277
1278
1279
1280
1281
1282
1283
1284
1285
1286
1287
1288
1289
1290
1291
1292
1293
1294
1295
1296
1297
1298
1299
1300
1301
1302
1303
1304
1305
1306
1307
1308
1309
1310
1311
1312
1313
1314
1315
1316
1317
1318
1319
1320
1321
1322
1323
1324
1325
1326
1327
1328
1329
1330
1331
1332
1333
1334
1335
1336
1337
1338
1339
1340
1341
1342
1343
1344
1345
1346
1347
1348
1349
1350
1351
1352
1353
1354
1355
1356
1357
1358
1359
1360
1361
1362
1363
1364
1365
1366
1367
1368
1369
1370
1371
1372
1373
1374
1375
1376
1377
1378
1379
1380
1381
1382
1383
1384
1385
1386
1387
1388
1389
1390
1391
1392
1393
1394
1395
1396
1397
1398
1399
1400
1401
1402
1403
1404
1405
1406
1407
1408
1409
1410
1411
1412
1413
1414
1415
1416
1417
1418
1419
1420
1421
1422
1423
1424
1425
1426
1427
1428
1429
1430
1431
1432
1433
1434
1435
1436
1437
1438
1439
1440
1441
1442
1443
1444
1445
1446
1447
1448
1449
1450
1451
1452
1453
1454
1455
1456
1457
1458
1459
1460
1461
1462
1463
1464
1465
1466
1467
1468
1469
1470
1471
1472
1473
1474
1475
1476
1477
1478
1479
1480
1481
1482
1483
1484
1485
1486
1487
1488
1489
1490
1491
1492
1493
1494
1495
1496
1497
1498
1499
1500
1501
1502
1503
1504
1505
1506
1507
1508
1509
1510
1511
1512
1513
1514
1515
1516
1517
1518
1519
1520
1521
1522
1523
1524
1525
1526
1527
1528
1529
1530
1531
1532
1533
1534
1535
1536
1537
1538
1539
1540
1541
1542
1543
1544
1545
1546
1547
1548
1549
1550
1551
1552
1553
1554
1555
1556
1557
1558
1559
1560
1561




                                           

                                                             



























                                                                           



                   

                         

                                   
 

                          

             
  

                      
                                                                   




                                                                     


              

                                                                              
                                                              
                                                                                          
                                                      
                                                                                  

                     
  











                                                                                        
   
 
                




                                     
                       
 
  
                                                                           
   
 






                                

                                                                                       
                    
 
















                                                                                             



                                                              
 









                                        
 
                                  
 


                   
 
               




                                                               

                
  










                              
  

                                                                                    

   



                             
                                                       
 
                





                                                                                  
                               
       
 



                                                                         
 


                                         


                                                                      
   

               
 
  
                   
   
 
                                                                                  
 

                                                       

 





                                                                                      


                                                                  
                                                                      




                                                                      
 


                          
                                                 













                                                          
 
 




                                                                            
 
                                               



                                       
 


                                                               
 

                                                                                             
                                                 






                                       
 


                                            
 




                                                                   
 



                                                     

                                                             
   
 


                                                                         
 
                                     
 




                                                             
 



                                                                          
                                                                        
 

                                 
 
  
                          

   
                                                           
 
                                           
 
 
  

                      

                                                                   
   
 
                                                                           
 

                                                                                                
 
                                        


                                                  
                                     
 



                                  

                      
                       
          






                                             
          
          
                                             
   






                                                                    



                                                      
 
 
















                                                                                   
                                     

 
  


                                                                      

   
                                                          
 
                                  
                                
 

                                               




                                                          
 
                                                

                                        
                                                           
                                     

                

 
  
                                                                     


                                                     
 


                                  
                                         
 
                                        
                                                                          

                                     



                
                                                             



                                                      

                                  
 
                                        
                                                       


                                     


  
                                                        
                                                          




                                                                      
   
 
                                                            
 


                                  








                                                                                                    
 
                                                      


  













                                                                                                

                      
                       













                                                                                    




























                                                                                               









                                                                       

   









                                                                       


                                                                
                                       

     


                                                             





                                                 
                             

                      


                                                                               
                                  



                                                                       
 
                                               







                                                                    

                                                      

                                          








                                              



                                                                    

       
                               

                                                                                      
                                          






                                             



                             
                                                

            
                                             
     
 



                                                          
                                                                


                       


                                                                      

       










                                                                      

                                                       
     






                                     





                                                                      



                                              
                                              



                                                         
                                              



                                          
                                              



                                              
                                               




                              
                          





                                                    




                                                                     

























                                                                      


                                              
 

                                                  
 


                                           
 
                                                                                                 

                 



                                                                                            
 











                                                                    
 
                                                      
 

                                           
 
                                                 

                   














                                                                                                
 











                                               
 







                                               
     
 







                                                                                               
 









                                                                                               

                                           




                                                     


                                                                                  

                                              
                                           
     
   
 


















                                                                      
 


                                        
 
                                                


                                                   
 
                                                            

                                       
 
                                                                            



                              
                                



























                                                                     
                
 
 


                                                                
                                                  

                                   
               
                

 
                                         
 

                                   
 
                
 
 











                                                                
 
                                         
                                                  
                                                                            
 








                                                                                                      
 

                                
 
                                                                                   




                                      
 
                                              



                                                 



                           
                                          
                        






                                                                                 




                                              
                                                                         
             
 
 



                                                                                
                                   
                                   
 



                       

                                                                                      

               
                                              
                                                                             
 
                            
 
                                     
 
                        
















                                     
                                                                      



                                                                                    
                      


                 



                                          
                                                   




                                   
             
 
                                                                                                  

               
                
 
                                                                                                 

               
                             
                                          

                             

                                           

                                                      


                                        

                                                              






                                                           

                       
 

                  
                                         



                                       
 

                                                       
 
                                                                                
               
 



                                                 


                   
                

 

                                                                                       
                                                                 





                                                                               
                                                                               
                                            





                                                                 
                                                                               
                                             






                                                         
                                         

                                                               


                                                         
                                                                       



                                                          
                                                                   
 











                                                                    




                                                               

               
                                                         























                                                                            
                          




                                                                              

                                                   
 

                                                                                               
 
                                                              
 
                            
                     








                                                                                  









                                                                              
                                               



                  
                

 




















































































































































































































































































































                                                                                                   
                                                            


                                     


                                                

















































































































                                                                                           







                                                 

           
                    
                   

   
  


                                                                         

   





                                                                    
 
                  

                                   





                                                       
 

                
 
  

                                                                     
   
 

                                                                      
                    
                                

                  

               
 




                                                                             
               
 
                              
 
                                               
                                
 




                                                                     


                                                                      
   
 
                                                     


                                                                             
                                                                                   
                                
 
               
 
                         
 
                                                     

 





                                                       
 
                  

                                   


                       
 

                                                    
 

                                          
 





                                                                            
 

                                   
 

                                                              
 
             

 
                               
 


                                                             




                                                                     





                                                                      
                                                              
 
                                       
                                          
 


                       
 

                                                    
 


                                          


                                     
                

 
                                                                            
 
                  

                                   

                                          
 





                                                    
 
                                          
 

                                   
 

                                               
 







                                                 
 








                                                    

 

                                        
 




                        
/*
 * 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, 0)) != 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_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)
          return err;
        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;
}

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_attributes,
  ks_get_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:
 */