array_index_nospec in Linux x86

Linux(tag v5.4)のソースコードリーディングをしていたときに面白いと思ったマクロのメモ．

array_index_nospec

include/linux/nospec.hで以下のように定義される．

/*
 * array_index_nospec - sanitize an array index after a bounds check
 *
 * For a code sequence like:
 *
 *     if (index < size) {
 *         index = array_index_nospec(index, size);
 *         val = array[index];
 *     }
 *
 * ...if the CPU speculates past the bounds check then
 * array_index_nospec() will clamp the index within the range of [0,
 * size).
 */
#define array_index_nospec(index, size)                                 \
({                                                                      \
        typeof(index) _i = (index);                                     \
        typeof(size) _s = (size);                                       \
        unsigned long _mask = array_index_mask_nospec(_i, _s);          \
                                                                        \
        BUILD_BUG_ON(sizeof(_i) > sizeof(long));                        \
        BUILD_BUG_ON(sizeof(_s) > sizeof(long));                        \
                                                                        \
        (typeof(_i)) (_i & _mask);                                      \
})

コメントにある通り，このマクロは配列のインデックス，サイズをそれぞれ引数index，sizeとして取り，indexがsize-1を超過していないかチェックする． もし超過していればidxを[0, size)の範囲に固定して（具体的には0を）返す．

実装としては引数indexを_l，sizeを_sに代入した後，array_index_mask_nospec()の引数として渡し，戻り値を_maskに代入し， その後，_l &_maskを返す．

x86においてはarray_index_mask_nospec()はarch/x86/include/asm/barrier.hに以下のように定義される．

/**
 * array_index_mask_nospec() - generate a mask that is ~0UL when the
 *      bounds check succeeds and 0 otherwise
 * @index: array element index
 * @size: number of elements in array
 *
 * Returns:
 *     0 - (index < size)
 */
static inline unsigned long array_index_mask_nospec(unsigned long index,
                unsigned long size)
{
        unsigned long mask;

        asm volatile ("cmp %1,%2; sbb %0,%0;"
                        :"=r" (mask)
                        :"g"(size),"r" (index)
                        :"cc");
        return mask;
}

array_index_mask_nospec()はインラインアセンブリで定義される．ここで実行されるアセンブリは以下のようになる．

cmp size, index;
sbb mask, mask;

cmp命令は減算index - sizeを行いフラグをセットするため，indexが正常値のときはCFがセットされる． sbb命令は第一オペランドから第二オペランドとCFを減算するため，indexが正常値のときはmaskに0UL-1UL=ULONG_MAXを，indexが配列のサイズを超えているときはmaskに0をセットする．

その後，array_index_nospecは_i & _maskをreturnする．

i.e. インデックスが配列のサイズを超えている時はindexは0とのビット論理積=0を返し，インデックスが正常値のときはindexとULONG_MAXとの論理積=indexを返す．

ありがちな処理が軽量なバイナリとなるように配慮されて実装されていることがわかる．恐らくこう書くとconditional jumpとかが消えるんじゃないかな．知らんけど．