Line data    Source code

       1             : #ifndef HEADER_fd_src_ballet_reedsol_fd_reedsol_h
       2             : #define HEADER_fd_src_ballet_reedsol_fd_reedsol_h
       3             : 
       4             : /* fd_reedsol provides APIs for producing Reed-Solomon encoded parity
       5             :    data and for reconstructing missing data from parity data.  The
       6             :    encoding process is optimized, and highly optimized for Turbine's
       7             :    typical case.
       8             : 
       9             :    Reed-Solomon works in GF(2^8), i.e. the codeword size is 1 byte, but
      10             :    is typically used on each byte of larger pieces of data called
      11             :    shreds (a Solana-specific term, often called shards elsewhere in the
      12             :    literature).  Mathematically, the encoding process forms a vector
      13             :    from the input data, taking one byte from each shred, and
      14             :    left-multiplies the vector by a constant matrix in GF(2^8).  The
      15             :    resulting vector contains one byte for each of the parity shreds.
      16             :    Solana also calls parity shreds "code" shreds, but due to the naming
      17             :    collision with executable code, we have opted for "parity."  This
      18             :    mathematical structure thus forces each shred to be of identical size
      19             :    but doesn't otherwise impose any size restrictions.*/
      20             : 
      21             : #include "../fd_ballet_base.h"
      22             : 
      23             : /* FD_REEDSOL_{DATA,PARITY}_SHREDS_MAX describe the inclusive maximum
      24             :    number of data and parity shreds that this implementation supports.
      25             :    These limits are not mathematical limits, but limits based on current
      26             :    Solana needs and performance.  The common case for both shred counts
      27             :    to be set to 32. */
      28             : 
      29       12255 : #define FD_REEDSOL_DATA_SHREDS_MAX   (67UL)
      30       12051 : #define FD_REEDSOL_PARITY_SHREDS_MAX (67UL)
      31             : 
      32             : #define FD_REEDSOL_ALIGN     (128UL)
      33             : #define FD_REEDSOL_FOOTPRINT (2304UL) /* 18*ALIGN */
      34             : 
      35             : /* FD_REEDSOL_SUCCESS, FD_REEDSOL_ERR_* are error code return values used
      36             :    by the recover operation, which is the only part that can fail for
      37             :    non-bug reasons.  Their meaning is documented with
      38             :    fd_reedsol_recover_fini.  SUCCESS must be zero, ERR_* are negative
      39             :    and distinct. */
      40             : 
      41          90 : #define FD_REEDSOL_SUCCESS     (0)
      42           0 : #define FD_REEDSOL_ERR_CORRUPT (-1)
      43           0 : #define FD_REEDSOL_ERR_PARTIAL (-2)
      44             : 
      45             : struct __attribute__((aligned(FD_REEDSOL_ALIGN))) fd_reedsol_private {
      46             :   uchar scratch[ 1024 ];  // Used for the ultra high performance implementation
      47             : 
      48             :   ulong shred_sz;         // shred_sz: the size of each shred in bytes (all shreds must be the same size)
      49             :   ulong data_shred_cnt;   // {data,parity}_shred_cnt: the number of data or parity shreds
      50             :   ulong parity_shred_cnt; // (respectively) have been added to the in-process operation
      51             : 
      52             :   union {
      53             : 
      54             :     struct {
      55             :       uchar const * data_shred  [ FD_REEDSOL_DATA_SHREDS_MAX   ]; // {data,parity}_shred: pointers to the 1st byte of each shred
      56             :       uchar *       parity_shred[ FD_REEDSOL_PARITY_SHREDS_MAX ];
      57             :     } encode;
      58             : 
      59             :     struct {
      60             :       uchar * shred[ FD_REEDSOL_DATA_SHREDS_MAX + FD_REEDSOL_PARITY_SHREDS_MAX ];
      61             :       /* erased: whether the shred at the corresponding index is an
      62             :          erasure (i.e. wasn't received or was corrupted).  Used only for
      63             :          decoding operations.  TODO: Is this the right data type? Should
      64             :          it use a fd_smallset instead? */
      65             :       uchar erased[ FD_REEDSOL_DATA_SHREDS_MAX + FD_REEDSOL_PARITY_SHREDS_MAX ];
      66             :     } recover;
      67             : 
      68             :   };
      69             : };
      70             : 
      71             : typedef struct fd_reedsol_private fd_reedsol_t;
      72             : 
      73             : FD_PROTOTYPES_BEGIN
      74             : 
      75             : /* fd_reedsol_{align,footprint} return the alignment and footprint
      76             :    required in bytes for a fd_reedsol_t. */
      77             : 
      78           0 : static inline FD_FN_CONST ulong fd_reedsol_align(     void ) { return FD_REEDSOL_ALIGN;     }
      79           0 : static inline FD_FN_CONST ulong fd_reedsol_footprint( void ) { return FD_REEDSOL_FOOTPRINT; }
      80             : 
      81             : /* fd_reedsol_encode_init: starts a Reed-Solomon encoding operation that
      82             :    will encode shreds of size shred_sz.  mem is assumed to be a piece of
      83             :    memory that meets the alignment and size constraints specified above.
      84             :    Takes a write interest in mem that persists until the operation is
      85             :    aborted or finalized.  shred_sz must be >= 32.  Returns mem as a a
      86             :    newly initialized encoder.  Every call to fd_reedsol_encode_init
      87             :    should be paired with a call to fd_reedsol_encode_fini (normal
      88             :    execution) or fd_reedsol_encode_abort (abnormal execution). */
      89             : 
      90             : static inline fd_reedsol_t *
      91             : fd_reedsol_encode_init( void * mem,
      92     1481274 :                         ulong  shred_sz ) {
      93     1481274 :   fd_reedsol_t * rs = (fd_reedsol_t *)mem;
      94     1481274 :   rs->shred_sz         = shred_sz;
      95     1481274 :   rs->data_shred_cnt   = 0UL;
      96     1481274 :   rs->parity_shred_cnt = 0UL;
      97     1481274 :   return rs;
      98     1481274 : }
      99             : 
     100             : /* fd_reedsol_encode_add_data_shred: adds a shred consisting of the
     101             :    memory [ptr,ptr+shred_sz) to the in-process Reed-Solomon encoding
     102             :    operation.  Takes a read interest in the shred that persists for the
     103             :    lifetime of the operation (i.e. until finalized or aborted).  Data
     104             :    shreds have no alignment restrictions and can overlap with each other
     105             :    but should not overlap with any parity shreds in the same encoding
     106             :    operation.
     107             : 
     108             :    Note: The order in which data shreds are added relative to other data
     109             :    shreds matters.  It impacts the parity data produced by the encoding
     110             :    operation.
     111             : 
     112             :    Assumes rs is initialized as an encoder and returns rs (still
     113             :    initialized as an encoder). */
     114             : 
     115             : static inline fd_reedsol_t *
     116             : fd_reedsol_encode_add_data_shred( fd_reedsol_t * rs,
     117    50278014 :                                   void const *   ptr ) {
     118    50278014 :   rs->encode.data_shred[ rs->data_shred_cnt++ ] = (uchar const*) ptr;
     119    50278014 :   return rs;
     120    50278014 : }
     121             : 
     122             : /* fd_reedsol_encode_add_parity_shred: adds the block of memory
     123             :    [ptr,ptr+shred_sz) to the in-process Reed-Solomon encoding operation
     124             :    as the destination of a parity shred.  Takes a write interest in the
     125             :    memory that persists for the lifetime of the operation (i.e. until
     126             :    finalized or aborted).  Parity shreds have no alignment
     127             :    restrictions but must not overlap with each other or with data shreds
     128             :    in the same operation (U.B. if they overlap).
     129             : 
     130             :    Note: The order in which parity shreds are added matters only insofar
     131             :    as which data will be written to which location.
     132             : 
     133             :    Assumes rs is initialized as an encoder and returns rs (still
     134             :    initialized as an encoder). */
     135             : 
     136             : static inline fd_reedsol_t *
     137             : fd_reedsol_encode_add_parity_shred( fd_reedsol_t * rs,
     138    51165684 :                                     void *         ptr ) {
     139    51165684 :   rs->encode.parity_shred[ rs->parity_shred_cnt++ ] = (uchar *)ptr;
     140    51165684 :   return rs;
     141    51165684 : }
     142             : 
     143             : /* fd_reedsol_encode_abort aborts an in-progress encoding operation.
     144             :    Releases any read or write interests in any shreds that were added to
     145             :    the operation.  Upon return, the contents of the parity shreds are
     146             :    undefined.  Assumes rs is initialized as an encoder, rs will not be
     147             :    initialized on return. */
     148             : 
     149             : static inline void
     150           0 : fd_reedsol_encode_abort( fd_reedsol_t * rs ) {
     151           0 :   rs->data_shred_cnt   = 0UL;
     152           0 :   rs->parity_shred_cnt = 0UL;
     153           0 : }
     154             : 
     155             : /* fd_reedsol_encode_fini finishes the in-progress encoding operation.
     156             :    Upon return, the parity shreds will be filled with the correct
     157             :    Reed-Solomon encoded parity data.  Upon return, this will no longer
     158             :    have any read or write interest in any of the provided shreds.
     159             :    Assumes rs is initialized as an encoder, rs will not be initialized
     160             :    on return. */
     161             : 
     162             : void
     163             : fd_reedsol_encode_fini( fd_reedsol_t * rs );
     164             : 
     165             : /* fd_reedsol_recover_init: starts a Reed-Solomon recover/decode
     166             :    operation that will recover shreds of size shred_sz.  mem is assumed
     167             :    to be an unused piece of memory that meets the alignment and size
     168             :    constraints specified above.  Takes a write interest in mem that
     169             :    persists until the operation is aborted or finalized.  shred_sz must
     170             :    be >= 32.  Returns mem as a newly initialized recoverer.  Every call
     171             :    to fd_reedsol_recover_init should be paired with a call to
     172             :    fd_reedsol_recover_fini (normal execution) or
     173             :    fd_reedsol_recover_abort (abnormal execution). */
     174             : 
     175             : static inline fd_reedsol_t *
     176          90 : fd_reedsol_recover_init( void * mem, ulong shred_sz ) {
     177          90 :   fd_reedsol_t * rs = (fd_reedsol_t *)mem;
     178          90 :   rs->shred_sz         = shred_sz;
     179          90 :   rs->data_shred_cnt   = 0UL;
     180          90 :   rs->parity_shred_cnt = 0UL;
     181          90 :   return rs;
     182          90 : }
     183             : 
     184             : /* fd_reedsol_recover_add_rcvd_shred adds the shred consisting of the of
     185             :    memory [ptr, ptr+shred_sz) to the in-process Reed-Solomon recover
     186             :    operation as a source of data.  Takes a read interest in the shred
     187             :    that persists for the lifetime of the operation (i.e. until finalized
     188             :    or aborted).  Received shreds have no alignment restrictions and can
     189             :    overlap with each other (if necessary, but there's no known use case
     190             :    for doing so), but should not overlap with any erased shreds in the
     191             :    same recovery operation.
     192             : 
     193             :    The shred is treated as a data shred if is_data_shred is non-zero and
     194             :    as a parity shred if not.  Data shreds and parity shreds are mostly
     195             :    treated identically in the recover operation, but having the right
     196             :    number of data shreds is important for validating the shreds are
     197             :    correct.
     198             : 
     199             :    Note: The order in which shreds are added (using this function and
     200             :    fd_reedsol_recover_add_erased_shred) is very important for recovery.
     201             :    Shreds must be added in the natural index order or the recover
     202             :    operation will almost certainly fail.  In particular, all data shreds
     203             :    must be added before any parity shreds are added.
     204             : 
     205             :    Assumes rs is initialized as a recoverer, returns rs (still
     206             :    initialized as a recoverer). */
     207             : 
     208             : static inline fd_reedsol_t *
     209             : fd_reedsol_recover_add_rcvd_shred( fd_reedsol_t * rs,
     210             :                                    int            is_data_shred,
     211        2790 :                                    void const *   ptr ) {
     212             : 
     213             :   /* Assumes is_data_shred==1 implies rs->parity_shred_cnt==0 and
     214             :      data_shred_cnt, parity_shred_cnt won't go over the max */
     215             : 
     216             :   /* For performance reasons, we need to store all the shred pointers in
     217             :      one flat array, which means the array needs to be non-const.  The
     218             :      const in the function signature signals that this operation won't
     219             :      modify the shred. */
     220             : 
     221        2790 :   rs->recover.shred [ rs->data_shred_cnt + rs->parity_shred_cnt ] = (void *)ptr;
     222        2790 :   rs->recover.erased[ rs->data_shred_cnt + rs->parity_shred_cnt ] = (uchar)0;
     223        2790 :   rs->data_shred_cnt   += !!is_data_shred;
     224        2790 :   rs->parity_shred_cnt +=  !is_data_shred;
     225             : 
     226        2790 :   return rs;
     227        2790 : }
     228             : 
     229             : /* fd_reedsol_recover_add_erased_shred adds the block of memory
     230             :    [ptr,ptr+shred_sz) to the in-process Reed-Solomon recover operation
     231             :    as the destination for a shred that will be recovered.  Takes a write
     232             :    interest in the shred that persists for the lifetime of the operation
     233             :    (i.e. until finalized or aborted).  Erased shreds have no alignment
     234             :    restrictions but should not overlap with any other shreds in the same
     235             :    recover operation.  The contents of the the block of memory are
     236             :    ignored and will be overwritten by the time the operation is
     237             :    finished.
     238             : 
     239             :    The shred is treated as a data shred if is_data_shred is non-zero and
     240             :    as a parity shred if not.  Data shreds and parity shreds are mostly
     241             :    treated identically in the recover operation, but having the right
     242             :    number of data shreds is important for validating the shreds are
     243             :    correct.
     244             : 
     245             :    Note: The order in which shreds are added (using this function and
     246             :    fd_reedsol_recover_add_rcvd_shred) is very important for recovery.
     247             :    Shreds must be added in the natural index order or the recover
     248             :    operation will almost certainly fail.  In particular, all data shreds
     249             :    must be added before any parity shreds are added.
     250             : 
     251             :    Assumes rs is initialized as a recoverer, returns rs (still
     252             :    initialized as a recoverer). */
     253             : 
     254             : static inline fd_reedsol_t *
     255             : fd_reedsol_recover_add_erased_shred( fd_reedsol_t * rs,
     256             :                                      int            is_data_shred,
     257        2856 :                                      void *         ptr ) {
     258             : 
     259             :   /* Assumes assert is_data_shred==1 implies rs->parity_shred_cnt==0 and
     260             :      data_shred_cnt, parity_shred_cnt won't go over the max */
     261             : 
     262        2856 :   rs->recover.shred [ rs->data_shred_cnt + rs->parity_shred_cnt ] = ptr;
     263        2856 :   rs->recover.erased[ rs->data_shred_cnt + rs->parity_shred_cnt ] = (uchar)1;
     264        2856 :   rs->data_shred_cnt   += !!is_data_shred;
     265        2856 :   rs->parity_shred_cnt +=  !is_data_shred;
     266             : 
     267        2856 :   return rs;
     268        2856 : }
     269             : 
     270             : /* fd_reedsol_recover_abort aborts an in-progress encoding operation.
     271             :    Releases any read or write interests in any shreds that were added to
     272             :    the operation.  Upon return, the contents of the erased shreds are
     273             :    undefined.  Assumes rs is initialized and rs will not be initialized
     274             :    on return. */
     275             : 
     276             : static inline void
     277           0 : fd_reedsol_recover_abort( fd_reedsol_t * rs ) {
     278           0 :   rs->data_shred_cnt   = 0UL;
     279           0 :   rs->parity_shred_cnt = 0UL;
     280           0 : }
     281             : 
     282             : /* fd_reedsol_recover_fini finishes the in-progress recover operation.
     283             :    If successful, upon return, any erased shreds will be filled with the
     284             :    correct data as recovered by the Reed-Solomon recovery algorithm.  If
     285             :    the recover operation fails with FD_REEDSOL_ERR_{CORRUPT,PARTIAL},
     286             :    the contents of any erased shreds are undefined.
     287             : 
     288             :    Upon return, this will no longer have any read or write interest in
     289             :    any of the provided shreds.
     290             : 
     291             :    Returns one of:
     292             : 
     293             :    FD_REEDSOL_SUCCESS if the recover operation was successful
     294             : 
     295             :    FD_REEDSOL_ERR_CORRUPT if the shreds are not consistent with having
     296             :    come from a Reed-Solomon encoding with the provided number of data
     297             :    shreds
     298             : 
     299             :    FD_REEDSOL_ERR_PARTIAL if there's not enough un-erased data to
     300             :    recover data_shred_cnt data shreds.  There must be at least one
     301             :    un-erased shred (data or parity) for each data shred in the
     302             :    operation.
     303             : 
     304             :    It's worth pointing out that the recovery process differs from
     305             :    typical network coding theory by making no effort to correct data
     306             :    corruption.  The shred signature verification process should detect
     307             :    any data corruption, and any shred that fails signature verification
     308             :    can be treated as an erasure.  This prevents the network from forking
     309             :    if the leader (maliciously) creates data shreds from one version of
     310             :    the block and parity shreds from another version of the block.
     311             : 
     312             :    Assumes rs is initialized as a recoverer, rs will not be initialized
     313             :    on return. */
     314             : 
     315             : int
     316             : fd_reedsol_recover_fini( fd_reedsol_t * rs );
     317             : 
     318             : /* Misc APIs */
     319             : 
     320             : /* fd_reedsol_strerror converts a FD_REEDSOL_SUCCESS / FD_REEDSOL_ERR_*
     321             :    code into a human readable cstr.  The lifetime of the returned
     322             :    pointer is infinite.  The returned pointer is always to a non-NULL
     323             :    cstr. */
     324             : 
     325             : FD_FN_CONST char const *
     326             : fd_reedsol_strerror( int err );
     327             : 
     328             : FD_PROTOTYPES_END
     329             : 
     330             : #endif /* HEADER_fd_src_ballet_reedsol_fd_reedsol_h */