1 /* ----> DO NOT REMOVE THE FOLLOWING NOTICE <----
2 *
3 * Copyright (c) 2014-2015 Datalight, Inc.
4 * All Rights Reserved Worldwide.
5 *
6 * This program is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License as published by
8 * the Free Software Foundation; use version 2 of the License.
9 *
10 * This program is distributed in the hope that it will be useful,
11 * but "AS-IS," WITHOUT ANY WARRANTY; without even the implied warranty
12 * of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 * GNU General Public License for more details.
14 *
15 * You should have received a copy of the GNU General Public License along
16 * with this program; if not, write to the Free Software Foundation, Inc.,
17 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
18 */
19
20 /* Businesses and individuals that for commercial or other reasons cannot
21 * comply with the terms of the GPLv2 license may obtain a commercial license
22 * before incorporating Reliance Edge into proprietary software for
23 * distribution in any form. Visit http://www.datalight.com/reliance-edge for
24 * more information.
25 */
26
27 /** @file
28 * @brief Implements the block device buffering system.
29 *
30 * This module implements the block buffer cache. It has a number of block
31 * sized buffers which are used to store data from a given block (identified
32 * by both block number and volume number: this cache is shared among all
33 * volumes). Block buffers may be either dirty or clean. Most I/O passes
34 * through this module. When a buffer is needed for a block which is not in
35 * the cache, a "victim" is selected via a simple LRU scheme.
36 */
37 #include <redfs.h>
38 #include <redcore.h>
39
40
41 #if DINDIR_POINTERS > 0U
42 #define INODE_META_BUFFERS 3U /* Inode, double indirect, indirect */
43 #elif REDCONF_INDIRECT_POINTERS > 0U
44 #define INODE_META_BUFFERS 2U /* Inode, indirect */
45 #elif REDCONF_DIRECT_POINTERS == INODE_ENTRIES
46 #define INODE_META_BUFFERS 1U /* Inode only */
47 #endif
48
49 #define INODE_BUFFERS ( INODE_META_BUFFERS + 1U ) /* Add data buffer */
50
51 #if REDCONF_IMAP_EXTERNAL == 1
52 #define IMAP_BUFFERS 1U
53 #else
54 #define IMAP_BUFFERS 0U
55 #endif
56
57 #if ( REDCONF_READ_ONLY == 1 ) || ( REDCONF_API_FSE == 1 )
58
59 /* Read, write, truncate, lookup: One inode all the way down, plus imap.
60 */
61 #define MINIMUM_BUFFER_COUNT ( INODE_BUFFERS + IMAP_BUFFERS )
62 #elif REDCONF_API_POSIX == 1
63 #if REDCONF_API_POSIX_RENAME == 1
64 #if REDCONF_RENAME_ATOMIC == 1
65
66 /* Two parent directories all the way down. Source and destination inode
67 * buffer. One inode buffer for cyclic rename detection. Imap. The
68 * parent inode buffers are released before deleting the destination
69 * inode, so that does not increase the minimum.
70 */
71 #define MINIMUM_BUFFER_COUNT ( INODE_BUFFERS + INODE_BUFFERS + 3U + IMAP_BUFFERS )
72 #else
73
74 /* Two parent directories all the way down. Source inode buffer. One
75 * inode buffer for cyclic rename detection. Imap.
76 */
77 #define MINIMUM_BUFFER_COUNT ( INODE_BUFFERS + INODE_BUFFERS + 2U + IMAP_BUFFERS )
78 #endif
79 #else
80
81 /* Link/create: Needs a parent inode all the way down, an extra inode
82 * buffer, and an imap buffer.
83 *
84 * Unlink is the same, since the parent inode buffers are released before
85 * the inode is deleted.
86 */
87 #define MINIMUM_BUFFER_COUNT ( INODE_BUFFERS + 1U + IMAP_BUFFERS )
88 #endif /* if REDCONF_API_POSIX_RENAME == 1 */
89 #endif /* if ( REDCONF_READ_ONLY == 1 ) || ( REDCONF_API_FSE == 1 ) */
90
91 #if REDCONF_BUFFER_COUNT < MINIMUM_BUFFER_COUNT
92 #error "REDCONF_BUFFER_COUNT is too low for the configuration"
93 #endif
94
95
96 /* A note on the typecasts in the below macros: Operands to bitwise operators
97 * are subject to the "usual arithmetic conversions". This means that the
98 * flags, which have uint16_t values, are promoted to int. MISRA-C:2012 R10.1
99 * forbids using signed integers in bitwise operations, so we cast to uint32_t
100 * to avoid the integer promotion, then back to uint16_t to reflect the actual
101 * type.
102 */
103 #define BFLAG_META_MASK ( uint16_t ) ( ( uint32_t ) BFLAG_META_MASTER | BFLAG_META_IMAP | BFLAG_META_INODE | BFLAG_META_INDIR | BFLAG_META_DINDIR )
104 #define BFLAG_MASK ( uint16_t ) ( ( uint32_t ) BFLAG_DIRTY | BFLAG_NEW | BFLAG_META_MASK )
105
106
107 /* An invalid block number. Used to indicate buffers which are not currently
108 * in use.
109 */
110 #define BBLK_INVALID UINT32_MAX
111
112
113 /** @brief Metadata stored for each block buffer.
114 *
115 * To make better use of CPU caching when searching the BUFFERHEAD array, this
116 * structure should be kept small.
117 */
118 typedef struct
119 {
120 uint32_t ulBlock; /**< Block number the buffer is associated with; BBLK_INVALID if unused. */
121 uint8_t bVolNum; /**< Volume the block resides on. */
122 uint8_t bRefCount; /**< Number of references. */
123 uint16_t uFlags; /**< Buffer flags: mask of BFLAG_* values. */
124 } BUFFERHEAD;
125
126
127 /** @brief State information for the block buffer module.
128 */
129 typedef struct
130 {
131 /** Number of buffers which are referenced (have a bRefCount > 0).
132 */
133 uint16_t uNumUsed;
134
135 /** MRU array. Each element of the array stores a buffer index; each buffer
136 * index appears in the array once and only once. The first element of the
137 * array is the most-recently-used (MRU) buffer, followed by the next most
138 * recently used, and so on, till the last element, which is the least-
139 * recently-used (LRU) buffer.
140 */
141 uint8_t abMRU[ REDCONF_BUFFER_COUNT ];
142
143 /** Buffer heads, storing metadata for each buffer.
144 */
145 BUFFERHEAD aHead[ REDCONF_BUFFER_COUNT ];
146
147 /** Array of memory for the block buffers themselves.
148 *
149 * Force 64-bit alignment of the aabBuffer array to ensure that it is safe
150 * to cast buffer pointers to node structure pointers.
151 */
152 ALIGNED_2D_BYTE_ARRAY( b, aabBuffer, REDCONF_BUFFER_COUNT, REDCONF_BLOCK_SIZE );
153 } BUFFERCTX;
154
155
156 static bool BufferIsValid( const uint8_t * pbBuffer,
157 uint16_t uFlags );
158 static bool BufferToIdx( const void * pBuffer,
159 uint8_t * pbIdx );
160 #if REDCONF_READ_ONLY == 0
161 static REDSTATUS BufferWrite( uint8_t bIdx );
162 static REDSTATUS BufferFinalize( uint8_t * pbBuffer,
163 uint16_t uFlags );
164 #endif
165 static void BufferMakeLRU( uint8_t bIdx );
166 static void BufferMakeMRU( uint8_t bIdx );
167 static bool BufferFind( uint32_t ulBlock,
168 uint8_t * pbIdx );
169
170 #ifdef REDCONF_ENDIAN_SWAP
171 static void BufferEndianSwap( const void * pBuffer,
172 uint16_t uFlags );
173 static void BufferEndianSwapHeader( NODEHEADER * pHeader );
174 static void BufferEndianSwapMaster( MASTERBLOCK * pMaster );
175 static void BufferEndianSwapMetaRoot( METAROOT * pMetaRoot );
176 static void BufferEndianSwapInode( INODE * pInode );
177 static void BufferEndianSwapIndir( INDIR * pIndir );
178 #endif
179
180
181 static BUFFERCTX gBufCtx;
182
183
184 /** @brief Initialize the buffers.
185 */
RedBufferInit(void)186 void RedBufferInit( void )
187 {
188 uint8_t bIdx;
189
190 RedMemSet( &gBufCtx, 0U, sizeof( gBufCtx ) );
191
192 for( bIdx = 0U; bIdx < REDCONF_BUFFER_COUNT; bIdx++ )
193 {
194 /* When the buffers have been freshly initialized, acquire the buffers
195 * in the order in which they appear in the array.
196 */
197 gBufCtx.abMRU[ bIdx ] = ( uint8_t ) ( ( REDCONF_BUFFER_COUNT - bIdx ) - 1U );
198 gBufCtx.aHead[ bIdx ].ulBlock = BBLK_INVALID;
199 }
200 }
201
202
203 /** @brief Acquire a buffer.
204 *
205 * @param ulBlock Block number to acquire.
206 * @param uFlags BFLAG_ values for the operation.
207 * @param ppBuffer On success, populated with the acquired buffer.
208 *
209 * @return A negated ::REDSTATUS code indicating the operation result.
210 *
211 * @retval 0 Operation was successful.
212 * @retval -RED_EIO A disk I/O error occurred.
213 * @retval -RED_EINVAL Invalid parameters.
214 * @retval -RED_EBUSY All buffers are referenced.
215 */
RedBufferGet(uint32_t ulBlock,uint16_t uFlags,void ** ppBuffer)216 REDSTATUS RedBufferGet( uint32_t ulBlock,
217 uint16_t uFlags,
218 void ** ppBuffer )
219 {
220 REDSTATUS ret = 0;
221 uint8_t bIdx;
222
223 if( ( ulBlock >= gpRedVolume->ulBlockCount ) || ( ( uFlags & BFLAG_MASK ) != uFlags ) || ( ppBuffer == NULL ) )
224 {
225 REDERROR();
226 ret = -RED_EINVAL;
227 }
228 else
229 {
230 if( BufferFind( ulBlock, &bIdx ) )
231 {
232 /* Error if the buffer exists and BFLAG_NEW was specified, since
233 * the new flag is used when a block is newly allocated/created, so
234 * the block was previously free and and there should never be an
235 * existing buffer for a free block.
236 *
237 * Error if the buffer exists but does not have the same type as
238 * was requested.
239 */
240 if( ( ( uFlags & BFLAG_NEW ) != 0U ) ||
241 ( ( uFlags & BFLAG_META_MASK ) != ( gBufCtx.aHead[ bIdx ].uFlags & BFLAG_META_MASK ) ) )
242 {
243 CRITICAL_ERROR();
244 ret = -RED_EFUBAR;
245 }
246 }
247 else if( gBufCtx.uNumUsed == REDCONF_BUFFER_COUNT )
248 {
249 /* The MINIMUM_BUFFER_COUNT is supposed to ensure that no operation
250 * ever runs out of buffers, so this should never happen.
251 */
252 CRITICAL_ERROR();
253 ret = -RED_EBUSY;
254 }
255 else
256 {
257 BUFFERHEAD * pHead;
258
259 /* Search for the least recently used buffer which is not
260 * referenced.
261 */
262 for( bIdx = ( uint8_t ) ( REDCONF_BUFFER_COUNT - 1U ); bIdx > 0U; bIdx-- )
263 {
264 if( gBufCtx.aHead[ gBufCtx.abMRU[ bIdx ] ].bRefCount == 0U )
265 {
266 break;
267 }
268 }
269
270 bIdx = gBufCtx.abMRU[ bIdx ];
271 pHead = &gBufCtx.aHead[ bIdx ];
272
273 if( pHead->bRefCount == 0U )
274 {
275 /* If the LRU buffer is valid and dirty, write it out before
276 * repurposing it.
277 */
278 if( ( ( pHead->uFlags & BFLAG_DIRTY ) != 0U ) && ( pHead->ulBlock != BBLK_INVALID ) )
279 {
280 #if REDCONF_READ_ONLY == 1
281 CRITICAL_ERROR();
282 ret = -RED_EFUBAR;
283 #else
284 ret = BufferWrite( bIdx );
285 #endif
286 }
287 }
288 else
289 {
290 /* All the buffers are used, which should have been caught by
291 * checking gBufCtx.uNumUsed.
292 */
293 CRITICAL_ERROR();
294 ret = -RED_EBUSY;
295 }
296
297 if( ret == 0 )
298 {
299 if( ( uFlags & BFLAG_NEW ) == 0U )
300 {
301 /* Invalidate the LRU buffer. If the read fails, we do not
302 * want the buffer head to continue to refer to the old
303 * block number, since the read, even if it fails, may have
304 * partially overwritten the buffer data (consider the case
305 * where block size exceeds sector size, and some but not
306 * all of the sectors are read successfully), and if the
307 * buffer were to be used subsequently with its partially
308 * erroneous contents, bad things could happen.
309 */
310 pHead->ulBlock = BBLK_INVALID;
311
312 ret = RedIoRead( gbRedVolNum, ulBlock, 1U, gBufCtx.b.aabBuffer[ bIdx ] );
313
314 if( ( ret == 0 ) && ( ( uFlags & BFLAG_META ) != 0U ) )
315 {
316 if( !BufferIsValid( gBufCtx.b.aabBuffer[ bIdx ], uFlags ) )
317 {
318 /* A corrupt metadata node is usually a critical
319 * error. The master block is an exception since
320 * it might be invalid because the volume is not
321 * mounted; that condition is expected and should
322 * not result in an assertion.
323 */
324 CRITICAL_ASSERT( ( uFlags & BFLAG_META_MASTER ) == BFLAG_META_MASTER );
325 ret = -RED_EIO;
326 }
327 }
328
329 #ifdef REDCONF_ENDIAN_SWAP
330 if( ret == 0 )
331 {
332 BufferEndianSwap( gBufCtx.b.aabBuffer[ bIdx ], uFlags );
333 }
334 #endif
335 }
336 else
337 {
338 RedMemSet( gBufCtx.b.aabBuffer[ bIdx ], 0U, REDCONF_BLOCK_SIZE );
339 }
340 }
341
342 if( ret == 0 )
343 {
344 pHead->bVolNum = gbRedVolNum;
345 pHead->ulBlock = ulBlock;
346 pHead->uFlags = 0U;
347 }
348 }
349
350 /* Reference the buffer, update its flags, and promote it to MRU. This
351 * happens both when BufferFind() found an existing buffer for the
352 * block and when the LRU buffer was repurposed to create a buffer for
353 * the block.
354 */
355 if( ret == 0 )
356 {
357 BUFFERHEAD * pHead = &gBufCtx.aHead[ bIdx ];
358
359 pHead->bRefCount++;
360
361 if( pHead->bRefCount == 1U )
362 {
363 gBufCtx.uNumUsed++;
364 }
365
366 /* BFLAG_NEW tells this function to zero the buffer instead of
367 * reading it from disk; it has no meaning later on, and thus is
368 * not saved.
369 */
370 pHead->uFlags |= ( uFlags & ( ~BFLAG_NEW ) );
371
372 BufferMakeMRU( bIdx );
373
374 *ppBuffer = gBufCtx.b.aabBuffer[ bIdx ];
375 }
376 }
377
378 return ret;
379 }
380
381
382 /** @brief Release a buffer.
383 *
384 * @param pBuffer The buffer to release.
385 */
RedBufferPut(const void * pBuffer)386 void RedBufferPut( const void * pBuffer )
387 {
388 uint8_t bIdx;
389
390 if( !BufferToIdx( pBuffer, &bIdx ) )
391 {
392 REDERROR();
393 }
394 else
395 {
396 REDASSERT( gBufCtx.aHead[ bIdx ].bRefCount > 0U );
397 gBufCtx.aHead[ bIdx ].bRefCount--;
398
399 if( gBufCtx.aHead[ bIdx ].bRefCount == 0U )
400 {
401 REDASSERT( gBufCtx.uNumUsed > 0U );
402 gBufCtx.uNumUsed--;
403 }
404 }
405 }
406
407
408 #if REDCONF_READ_ONLY == 0
409
410 /** @brief Flush all buffers for the active volume in the given range of blocks.
411 *
412 * @param ulBlockStart Starting block number to flush.
413 * @param ulBlockCount Count of blocks, starting at @p ulBlockStart, to flush.
414 * Must not be zero.
415 *
416 * @return A negated ::REDSTATUS code indicating the operation result.
417 *
418 * @retval 0 Operation was successful.
419 * @retval -RED_EIO A disk I/O error occurred.
420 * @retval -RED_EINVAL Invalid parameters.
421 */
RedBufferFlush(uint32_t ulBlockStart,uint32_t ulBlockCount)422 REDSTATUS RedBufferFlush( uint32_t ulBlockStart,
423 uint32_t ulBlockCount )
424 {
425 REDSTATUS ret = 0;
426
427 if( ( ulBlockStart >= gpRedVolume->ulBlockCount ) ||
428 ( ( gpRedVolume->ulBlockCount - ulBlockStart ) < ulBlockCount ) ||
429 ( ulBlockCount == 0U ) )
430 {
431 REDERROR();
432 ret = -RED_EINVAL;
433 }
434 else
435 {
436 uint8_t bIdx;
437
438 for( bIdx = 0U; bIdx < REDCONF_BUFFER_COUNT; bIdx++ )
439 {
440 BUFFERHEAD * pHead = &gBufCtx.aHead[ bIdx ];
441
442 if( ( pHead->bVolNum == gbRedVolNum ) &&
443 ( pHead->ulBlock != BBLK_INVALID ) &&
444 ( ( pHead->uFlags & BFLAG_DIRTY ) != 0U ) &&
445 ( pHead->ulBlock >= ulBlockStart ) &&
446 ( pHead->ulBlock < ( ulBlockStart + ulBlockCount ) ) )
447 {
448 ret = BufferWrite( bIdx );
449
450 if( ret == 0 )
451 {
452 pHead->uFlags &= ( ~BFLAG_DIRTY );
453 }
454 else
455 {
456 break;
457 }
458 }
459 }
460 }
461
462 return ret;
463 }
464
465
466 /** @brief Mark a buffer dirty
467 *
468 * @param pBuffer The buffer to mark dirty.
469 */
RedBufferDirty(const void * pBuffer)470 void RedBufferDirty( const void * pBuffer )
471 {
472 uint8_t bIdx;
473
474 if( !BufferToIdx( pBuffer, &bIdx ) )
475 {
476 REDERROR();
477 }
478 else
479 {
480 REDASSERT( gBufCtx.aHead[ bIdx ].bRefCount > 0U );
481
482 gBufCtx.aHead[ bIdx ].uFlags |= BFLAG_DIRTY;
483 }
484 }
485
486
487 /** @brief Branch a buffer, marking it dirty and assigning a new block number.
488 *
489 * @param pBuffer The buffer to branch.
490 * @param ulBlockNew The new block number for the buffer.
491 */
RedBufferBranch(const void * pBuffer,uint32_t ulBlockNew)492 void RedBufferBranch( const void * pBuffer,
493 uint32_t ulBlockNew )
494 {
495 uint8_t bIdx;
496
497 if( !BufferToIdx( pBuffer, &bIdx ) ||
498 ( ulBlockNew >= gpRedVolume->ulBlockCount ) )
499 {
500 REDERROR();
501 }
502 else
503 {
504 BUFFERHEAD * pHead = &gBufCtx.aHead[ bIdx ];
505
506 REDASSERT( pHead->bRefCount > 0U );
507 REDASSERT( ( pHead->uFlags & BFLAG_DIRTY ) == 0U );
508
509 pHead->uFlags |= BFLAG_DIRTY;
510 pHead->ulBlock = ulBlockNew;
511 }
512 }
513
514
515 #if ( REDCONF_API_POSIX == 1 ) || FORMAT_SUPPORTED
516
517 /** @brief Discard a buffer, releasing it and marking it invalid.
518 *
519 * @param pBuffer The buffer to discard.
520 */
RedBufferDiscard(const void * pBuffer)521 void RedBufferDiscard( const void * pBuffer )
522 {
523 uint8_t bIdx;
524
525 if( !BufferToIdx( pBuffer, &bIdx ) )
526 {
527 REDERROR();
528 }
529 else
530 {
531 REDASSERT( gBufCtx.aHead[ bIdx ].bRefCount == 1U );
532 REDASSERT( gBufCtx.uNumUsed > 0U );
533
534 gBufCtx.aHead[ bIdx ].bRefCount = 0U;
535 gBufCtx.aHead[ bIdx ].ulBlock = BBLK_INVALID;
536
537 gBufCtx.uNumUsed--;
538
539 BufferMakeLRU( bIdx );
540 }
541 }
542 #endif /* if ( REDCONF_API_POSIX == 1 ) || FORMAT_SUPPORTED */
543 #endif /* REDCONF_READ_ONLY == 0 */
544
545
546 /** @brief Discard a range of buffers, marking them invalid.
547 *
548 * @param ulBlockStart The starting block number to discard
549 * @param ulBlockCount The number of blocks, starting at @p ulBlockStart, to
550 * discard. Must not be zero.
551 *
552 * @return A negated ::REDSTATUS code indicating the operation result.
553 *
554 * @retval 0 Operation was successful.
555 * @retval -RED_EINVAL Invalid parameters.
556 * @retval -RED_EBUSY A block in the desired range is referenced.
557 */
RedBufferDiscardRange(uint32_t ulBlockStart,uint32_t ulBlockCount)558 REDSTATUS RedBufferDiscardRange( uint32_t ulBlockStart,
559 uint32_t ulBlockCount )
560 {
561 REDSTATUS ret = 0;
562
563 if( ( ulBlockStart >= gpRedVolume->ulBlockCount ) ||
564 ( ( gpRedVolume->ulBlockCount - ulBlockStart ) < ulBlockCount ) ||
565 ( ulBlockCount == 0U ) )
566 {
567 REDERROR();
568 ret = -RED_EINVAL;
569 }
570 else
571 {
572 uint8_t bIdx;
573
574 for( bIdx = 0U; bIdx < REDCONF_BUFFER_COUNT; bIdx++ )
575 {
576 BUFFERHEAD * pHead = &gBufCtx.aHead[ bIdx ];
577
578 if( ( pHead->bVolNum == gbRedVolNum ) &&
579 ( pHead->ulBlock != BBLK_INVALID ) &&
580 ( pHead->ulBlock >= ulBlockStart ) &&
581 ( pHead->ulBlock < ( ulBlockStart + ulBlockCount ) ) )
582 {
583 if( pHead->bRefCount == 0U )
584 {
585 pHead->ulBlock = BBLK_INVALID;
586
587 BufferMakeLRU( bIdx );
588 }
589 else
590 {
591 /* This should never happen. There are three general cases
592 * when this function is used:
593 *
594 * 1) Discarding every block, as happens during unmount
595 * and at the end of format. There should no longer be
596 * any referenced buffers at those points.
597 * 2) Discarding a block which has become free. All
598 * buffers for such blocks should be put or branched
599 * beforehand.
600 * 3) Discarding of blocks that were just written straight
601 * to disk, leaving stale data in the buffer. The write
602 * code should never reference buffers for these blocks,
603 * since they would not be needed or used.
604 */
605 CRITICAL_ERROR();
606 ret = -RED_EBUSY;
607 break;
608 }
609 }
610 }
611 }
612
613 return ret;
614 }
615
616
617 /** Determine whether a metadata buffer is valid.
618 *
619 * This includes checking its signature, CRC, and sequence number.
620 *
621 * @param pbBuffer Pointer to the metadata buffer to validate.
622 * @param uFlags The buffer flags provided by the caller. Used to determine
623 * the expected signature.
624 *
625 * @return Whether the metadata buffer is valid.
626 *
627 * @retval true The metadata buffer is valid.
628 * @retval false The metadata buffer is invalid.
629 */
BufferIsValid(const uint8_t * pbBuffer,uint16_t uFlags)630 static bool BufferIsValid( const uint8_t * pbBuffer,
631 uint16_t uFlags )
632 {
633 bool fValid;
634
635 if( ( pbBuffer == NULL ) || ( ( uFlags & BFLAG_MASK ) != uFlags ) )
636 {
637 REDERROR();
638 fValid = false;
639 }
640 else
641 {
642 NODEHEADER buf;
643 uint16_t uMetaFlags = uFlags & BFLAG_META_MASK;
644
645 /* Casting pbBuffer to (NODEHEADER *) would run afoul MISRA-C:2012
646 * R11.3, so instead copy the fields out.
647 */
648 RedMemCpy( &buf.ulSignature, &pbBuffer[ NODEHEADER_OFFSET_SIG ], sizeof( buf.ulSignature ) );
649 RedMemCpy( &buf.ulCRC, &pbBuffer[ NODEHEADER_OFFSET_CRC ], sizeof( buf.ulCRC ) );
650 RedMemCpy( &buf.ullSequence, &pbBuffer[ NODEHEADER_OFFSET_SEQ ], sizeof( buf.ullSequence ) );
651
652 #ifdef REDCONF_ENDIAN_SWAP
653 buf.ulCRC = RedRev32( buf.ulCRC );
654 buf.ulSignature = RedRev32( buf.ulSignature );
655 buf.ullSequence = RedRev64( buf.ullSequence );
656 #endif
657
658 /* Make sure the signature is correct for the type of metadata block
659 * requested by the caller.
660 */
661 switch( buf.ulSignature )
662 {
663 case META_SIG_MASTER:
664 fValid = ( uMetaFlags == BFLAG_META_MASTER );
665 break;
666
667 #if REDCONF_IMAP_EXTERNAL == 1
668 case META_SIG_IMAP:
669 fValid = ( uMetaFlags == BFLAG_META_IMAP );
670 break;
671 #endif
672 case META_SIG_INODE:
673 fValid = ( uMetaFlags == BFLAG_META_INODE );
674 break;
675
676 #if DINDIR_POINTERS > 0U
677 case META_SIG_DINDIR:
678 fValid = ( uMetaFlags == BFLAG_META_DINDIR );
679 break;
680 #endif
681 #if REDCONF_DIRECT_POINTERS < INODE_ENTRIES
682 case META_SIG_INDIR:
683 fValid = ( uMetaFlags == BFLAG_META_INDIR );
684 break;
685 #endif
686 default:
687 fValid = false;
688 break;
689 }
690
691 if( fValid )
692 {
693 uint32_t ulComputedCrc;
694
695 /* Check for disk corruption by comparing the stored CRC with one
696 * computed from the data.
697 *
698 * Also check the sequence number: if it is greater than the
699 * current sequence number, the block is from a previous format
700 * or the disk is writing blocks out of order. During mount,
701 * before the metaroots have been read, the sequence number will
702 * be unknown, and the check is skipped.
703 */
704 ulComputedCrc = RedCrcNode( pbBuffer );
705
706 if( buf.ulCRC != ulComputedCrc )
707 {
708 fValid = false;
709 }
710 else if( gpRedVolume->fMounted && ( buf.ullSequence >= gpRedVolume->ullSequence ) )
711 {
712 fValid = false;
713 }
714 else
715 {
716 /* Buffer is valid. No action, fValid is already true.
717 */
718 }
719 }
720 }
721
722 return fValid;
723 }
724
725
726 /** @brief Derive the index of the buffer.
727 *
728 * @param pBuffer The buffer to derive the index of.
729 * @param pbIdx On success, populated with the index of the buffer.
730 *
731 * @return Boolean indicating result.
732 *
733 * @retval true Success.
734 * @retval false Failure. @p pBuffer is not a valid buffer pointer.
735 */
BufferToIdx(const void * pBuffer,uint8_t * pbIdx)736 static bool BufferToIdx( const void * pBuffer,
737 uint8_t * pbIdx )
738 {
739 bool fRet = false;
740
741 if( ( pBuffer != NULL ) && ( pbIdx != NULL ) )
742 {
743 uint8_t bIdx;
744
745 /* pBuffer should be a pointer to one of the block buffers.
746 *
747 * A good compiler should optimize this loop into a bounds check and an
748 * alignment check, although GCC has been observed to not do so; if the
749 * number of buffers is small, it should not make much difference. The
750 * alternative is to use pointer comparisons, but this both deviates
751 * from MISRA-C:2012 and involves undefined behavior.
752 */
753 for( bIdx = 0U; bIdx < REDCONF_BUFFER_COUNT; bIdx++ )
754 {
755 if( pBuffer == &gBufCtx.b.aabBuffer[ bIdx ][ 0U ] )
756 {
757 break;
758 }
759 }
760
761 if( ( bIdx < REDCONF_BUFFER_COUNT ) &&
762 ( gBufCtx.aHead[ bIdx ].ulBlock != BBLK_INVALID ) &&
763 ( gBufCtx.aHead[ bIdx ].bVolNum == gbRedVolNum ) )
764 {
765 *pbIdx = bIdx;
766 fRet = true;
767 }
768 }
769
770 return fRet;
771 }
772
773
774 #if REDCONF_READ_ONLY == 0
775
776 /** @brief Write out a dirty buffer.
777 *
778 * @param bIdx The index of the buffer to write.
779 *
780 * @return A negated ::REDSTATUS code indicating the operation result.
781 *
782 * @retval 0 Operation was successful.
783 * @retval -RED_EIO A disk I/O error occurred.
784 * @retval -RED_EINVAL Invalid parameters.
785 */
BufferWrite(uint8_t bIdx)786 static REDSTATUS BufferWrite( uint8_t bIdx )
787 {
788 REDSTATUS ret = 0;
789
790 if( bIdx < REDCONF_BUFFER_COUNT )
791 {
792 const BUFFERHEAD * pHead = &gBufCtx.aHead[ bIdx ];
793
794 REDASSERT( ( pHead->uFlags & BFLAG_DIRTY ) != 0U );
795
796 if( ( pHead->uFlags & BFLAG_META ) != 0U )
797 {
798 ret = BufferFinalize( gBufCtx.b.aabBuffer[ bIdx ], pHead->uFlags );
799 }
800
801 if( ret == 0 )
802 {
803 ret = RedIoWrite( pHead->bVolNum, pHead->ulBlock, 1U, gBufCtx.b.aabBuffer[ bIdx ] );
804
805 #ifdef REDCONF_ENDIAN_SWAP
806 BufferEndianSwap( gBufCtx.b.aabBuffer[ bIdx ], pHead->uFlags );
807 #endif
808 }
809 }
810 else
811 {
812 REDERROR();
813 ret = -RED_EINVAL;
814 }
815
816 return ret;
817 }
818
819
820 /** @brief Finalize a metadata buffer.
821 *
822 * This updates the CRC and the sequence number. It also sets the signature,
823 * though this is only truly needed if the buffer is new.
824 *
825 * @param pbBuffer Pointer to the metadata buffer to finalize.
826 * @param uFlags The associated buffer flags. Used to determine the expected
827 * signature.
828 *
829 * @return A negated ::REDSTATUS code indicating the operation result.
830 *
831 * @retval 0 Operation was successful.
832 * @retval -RED_EINVAL Invalid parameter; or maximum sequence number reached.
833 */
BufferFinalize(uint8_t * pbBuffer,uint16_t uFlags)834 static REDSTATUS BufferFinalize( uint8_t * pbBuffer,
835 uint16_t uFlags )
836 {
837 REDSTATUS ret = 0;
838
839 if( ( pbBuffer == NULL ) || ( ( uFlags & BFLAG_MASK ) != uFlags ) )
840 {
841 REDERROR();
842 ret = -RED_EINVAL;
843 }
844 else
845 {
846 uint32_t ulSignature;
847
848 switch( uFlags & BFLAG_META_MASK )
849 {
850 case BFLAG_META_MASTER:
851 ulSignature = META_SIG_MASTER;
852 break;
853
854 #if REDCONF_IMAP_EXTERNAL == 1
855 case BFLAG_META_IMAP:
856 ulSignature = META_SIG_IMAP;
857 break;
858 #endif
859 case BFLAG_META_INODE:
860 ulSignature = META_SIG_INODE;
861 break;
862
863 #if DINDIR_POINTERS > 0U
864 case BFLAG_META_DINDIR:
865 ulSignature = META_SIG_DINDIR;
866 break;
867 #endif
868 #if REDCONF_DIRECT_POINTERS < INODE_ENTRIES
869 case BFLAG_META_INDIR:
870 ulSignature = META_SIG_INDIR;
871 break;
872 #endif
873 default:
874 ulSignature = 0U;
875 break;
876 }
877
878 if( ulSignature == 0U )
879 {
880 REDERROR();
881 ret = -RED_EINVAL;
882 }
883 else
884 {
885 uint64_t ullSeqNum = gpRedVolume->ullSequence;
886
887 ret = RedVolSeqNumIncrement();
888
889 if( ret == 0 )
890 {
891 uint32_t ulCrc;
892
893 RedMemCpy( &pbBuffer[ NODEHEADER_OFFSET_SIG ], &ulSignature, sizeof( ulSignature ) );
894 RedMemCpy( &pbBuffer[ NODEHEADER_OFFSET_SEQ ], &ullSeqNum, sizeof( ullSeqNum ) );
895
896 #ifdef REDCONF_ENDIAN_SWAP
897 BufferEndianSwap( pbBuffer, uFlags );
898 #endif
899
900 ulCrc = RedCrcNode( pbBuffer );
901 #ifdef REDCONF_ENDIAN_SWAP
902 ulCrc = RedRev32( ulCrc );
903 #endif
904 RedMemCpy( &pbBuffer[ NODEHEADER_OFFSET_CRC ], &ulCrc, sizeof( ulCrc ) );
905 }
906 }
907 }
908
909 return ret;
910 }
911 #endif /* REDCONF_READ_ONLY == 0 */
912
913
914 #ifdef REDCONF_ENDIAN_SWAP
915
916 /** @brief Swap the byte order of a metadata buffer
917 *
918 * Does nothing if the buffer is not a metadata node. Also does nothing for
919 * meta roots, which don't go through the buffers anyways.
920 *
921 * @param pBuffer Pointer to the metadata buffer to swap
922 * @param uFlags The associated buffer flags. Used to determin the type of
923 * metadata node.
924 */
BufferEndianSwap(void * pBuffer,uint16_t uFlags)925 static void BufferEndianSwap( void * pBuffer,
926 uint16_t uFlags )
927 {
928 if( ( pBuffer == NULL ) || ( ( uFlags & BFLAG_MASK ) != uFlags ) )
929 {
930 REDERROR();
931 }
932 else if( ( uFlags & BFLAG_META_MASK ) != 0 )
933 {
934 BufferEndianSwapHeader( pBuffer );
935
936 switch( uFlags & BFLAG_META_MASK )
937 {
938 case BFLAG_META_MASTER:
939 BufferEndianSwapMaster( pBuffer );
940 break;
941
942 case BFLAG_META_INODE:
943 BufferEndianSwapInode( pBuffer );
944 break;
945
946 #if DINDIR_POINTERS > 0U
947 case BFLAG_META_DINDIR:
948 BufferEndianSwapIndir( pBuffer );
949 break;
950 #endif
951 #if REDCONF_DIRECT_POINTERS < INODE_ENTRIES
952 case BFLAG_META_INDIR:
953 BufferEndianSwapIndir( pBuffer );
954 break;
955 #endif
956 default:
957 break;
958 }
959 }
960 else
961 {
962 /* File data buffers do not need to be swapped.
963 */
964 }
965 }
966
967
968 /** @brief Swap the byte order of a metadata node header
969 *
970 * @param pHeader Pointer to the metadata node header to swap
971 */
BufferEndianSwapHeader(NODEHEADER * pHeader)972 static void BufferEndianSwapHeader( NODEHEADER * pHeader )
973 {
974 if( pHeader == NULL )
975 {
976 REDERROR();
977 }
978 else
979 {
980 pHeader->ulSignature = RedRev32( pHeader->ulSignature );
981 pHeader->ulCRC = RedRev32( pHeader->ulCRC );
982 pHeader->ullSequence = RedRev64( pHeader->ullSequence );
983 }
984 }
985
986
987 /** @brief Swap the byte order of a master block
988 *
989 * @param pMaster Pointer to the master block to swap
990 */
BufferEndianSwapMaster(MASTERBLOCK * pMaster)991 static void BufferEndianSwapMaster( MASTERBLOCK * pMaster )
992 {
993 if( pMaster == NULL )
994 {
995 REDERROR();
996 }
997 else
998 {
999 pMaster->ulVersion = RedRev32( pMaster->ulVersion );
1000 pMaster->ulFormatTime = RedRev32( pMaster->ulFormatTime );
1001 pMaster->ulInodeCount = RedRev32( pMaster->ulInodeCount );
1002 pMaster->ulBlockCount = RedRev32( pMaster->ulBlockCount );
1003 pMaster->uMaxNameLen = RedRev16( pMaster->uMaxNameLen );
1004 pMaster->uDirectPointers = RedRev16( pMaster->uDirectPointers );
1005 pMaster->uIndirectPointers = RedRev16( pMaster->uIndirectPointers );
1006 }
1007 }
1008
1009
1010 /** @brief Swap the byte order of an inode
1011 *
1012 * @param pInode Pointer to the inode to swap
1013 */
BufferEndianSwapInode(INODE * pInode)1014 static void BufferEndianSwapInode( INODE * pInode )
1015 {
1016 if( pInode == NULL )
1017 {
1018 REDERROR();
1019 }
1020 else
1021 {
1022 uint32_t ulIdx;
1023
1024 pInode->ullSize = RedRev64( pInode->ullSize );
1025
1026 #if REDCONF_INODE_BLOCKS == 1
1027 pInode->ulBlocks = RedRev32( pInode->ulBlocks );
1028 #endif
1029
1030 #if REDCONF_INODE_TIMESTAMPS == 1
1031 pInode->ulATime = RedRev32( pInode->ulATime );
1032 pInode->ulMTime = RedRev32( pInode->ulMTime );
1033 pInode->ulCTime = RedRev32( pInode->ulCTime );
1034 #endif
1035
1036 pInode->uMode = RedRev16( pInode->uMode );
1037
1038 #if ( REDCONF_API_POSIX == 1 ) && ( REDCONF_API_POSIX_LINK == 1 )
1039 pInode->uNLink = RedRev16( pInode->uNLink );
1040 #endif
1041
1042 #if REDCONF_API_POSIX == 1
1043 pInode->ulPInode = RedRev32( pInode->ulPInode );
1044 #endif
1045
1046 for( ulIdx = 0; ulIdx < INODE_ENTRIES; ulIdx++ )
1047 {
1048 pInode->aulEntries[ ulIdx ] = RedRev32( pInode->aulEntries[ ulIdx ] );
1049 }
1050 }
1051 }
1052
1053
1054 #if REDCONF_DIRECT_POINTERS < INODE_ENTRIES
1055
1056 /** @brief Swap the byte order of an indirect or double indirect node
1057 *
1058 * @param pIndir Pointer to the node to swap
1059 */
BufferEndianSwapIndir(INDIR * pIndir)1060 static void BufferEndianSwapIndir( INDIR * pIndir )
1061 {
1062 if( pIndir == NULL )
1063 {
1064 REDERROR();
1065 }
1066 else
1067 {
1068 uint32_t ulIdx;
1069
1070 pIndir->ulInode = RedRev32( pIndir->ulInode );
1071
1072 for( ulIdx = 0; ulIdx < INDIR_ENTRIES; ulIdx++ )
1073 {
1074 pIndir->aulEntries[ ulIdx ] = RedRev32( pIndir->aulEntries[ ulIdx ] );
1075 }
1076 }
1077 }
1078
1079 #endif /* REDCONF_DIRECT_POINTERS < INODE_ENTRIES */
1080 #endif /* #ifdef REDCONF_ENDIAN_SWAP */
1081
1082
1083 /** @brief Mark a buffer as least recently used.
1084 *
1085 * @param bIdx The index of the buffer to make LRU.
1086 */
BufferMakeLRU(uint8_t bIdx)1087 static void BufferMakeLRU( uint8_t bIdx )
1088 {
1089 if( bIdx >= REDCONF_BUFFER_COUNT )
1090 {
1091 REDERROR();
1092 }
1093 else if( bIdx != gBufCtx.abMRU[ REDCONF_BUFFER_COUNT - 1U ] )
1094 {
1095 uint8_t bMruIdx;
1096
1097 /* Find the current position of the buffer in the MRU array. We do not
1098 * need to check the last slot, since we already know from the above
1099 * check that the index is not there.
1100 */
1101 for( bMruIdx = 0U; bMruIdx < ( REDCONF_BUFFER_COUNT - 1U ); bMruIdx++ )
1102 {
1103 if( bIdx == gBufCtx.abMRU[ bMruIdx ] )
1104 {
1105 break;
1106 }
1107 }
1108
1109 if( bMruIdx < ( REDCONF_BUFFER_COUNT - 1U ) )
1110 {
1111 /* Move the buffer index to the back of the MRU array, making it
1112 * the LRU buffer.
1113 */
1114 RedMemMove( &gBufCtx.abMRU[ bMruIdx ], &gBufCtx.abMRU[ bMruIdx + 1U ], REDCONF_BUFFER_COUNT - ( ( uint32_t ) bMruIdx + 1U ) );
1115 gBufCtx.abMRU[ REDCONF_BUFFER_COUNT - 1U ] = bIdx;
1116 }
1117 else
1118 {
1119 REDERROR();
1120 }
1121 }
1122 else
1123 {
1124 /* Buffer already LRU, nothing to do.
1125 */
1126 }
1127 }
1128
1129
1130 /** @brief Mark a buffer as most recently used.
1131 *
1132 * @param bIdx The index of the buffer to make MRU.
1133 */
BufferMakeMRU(uint8_t bIdx)1134 static void BufferMakeMRU( uint8_t bIdx )
1135 {
1136 if( bIdx >= REDCONF_BUFFER_COUNT )
1137 {
1138 REDERROR();
1139 }
1140 else if( bIdx != gBufCtx.abMRU[ 0U ] )
1141 {
1142 uint8_t bMruIdx;
1143
1144 /* Find the current position of the buffer in the MRU array. We do not
1145 * need to check the first slot, since we already know from the above
1146 * check that the index is not there.
1147 */
1148 for( bMruIdx = 1U; bMruIdx < REDCONF_BUFFER_COUNT; bMruIdx++ )
1149 {
1150 if( bIdx == gBufCtx.abMRU[ bMruIdx ] )
1151 {
1152 break;
1153 }
1154 }
1155
1156 if( bMruIdx < REDCONF_BUFFER_COUNT )
1157 {
1158 /* Move the buffer index to the front of the MRU array, making it
1159 * the MRU buffer.
1160 */
1161 RedMemMove( &gBufCtx.abMRU[ 1U ], &gBufCtx.abMRU[ 0U ], bMruIdx );
1162 gBufCtx.abMRU[ 0U ] = bIdx;
1163 }
1164 else
1165 {
1166 REDERROR();
1167 }
1168 }
1169 else
1170 {
1171 /* Buffer already MRU, nothing to do.
1172 */
1173 }
1174 }
1175
1176
1177 /** @brief Find a block in the buffers.
1178 *
1179 * @param ulBlock The block number to find.
1180 * @param pbIdx If the block is buffered (true is returned), populated with
1181 * the index of the buffer.
1182 *
1183 * @return Boolean indicating whether or not the block is buffered.
1184 *
1185 * @retval true @p ulBlock is buffered, and its index has been stored in
1186 * @p pbIdx.
1187 * @retval false @p ulBlock is not buffered.
1188 */
BufferFind(uint32_t ulBlock,uint8_t * pbIdx)1189 static bool BufferFind( uint32_t ulBlock,
1190 uint8_t * pbIdx )
1191 {
1192 bool ret = false;
1193
1194 if( ( ulBlock >= gpRedVolume->ulBlockCount ) || ( pbIdx == NULL ) )
1195 {
1196 REDERROR();
1197 }
1198 else
1199 {
1200 uint8_t bIdx;
1201
1202 for( bIdx = 0U; bIdx < REDCONF_BUFFER_COUNT; bIdx++ )
1203 {
1204 const BUFFERHEAD * pHead = &gBufCtx.aHead[ bIdx ];
1205
1206 if( ( pHead->bVolNum == gbRedVolNum ) && ( pHead->ulBlock == ulBlock ) )
1207 {
1208 *pbIdx = bIdx;
1209 ret = true;
1210 break;
1211 }
1212 }
1213 }
1214
1215 return ret;
1216 }
1217