Open3

Linux Kernel の linked list の実装

ぷるぷる

include/linux/list.h の実装を読む。正確には Circular doubly linked list らしい。
各ノード(head?)は前後のノードのポインタを持つ。先頭ノードには前のノード、末尾ノードには後ろのノードが存在しないが、それぞれ末尾ノード、先頭ノードを持つことにする。

ぷるぷる

様々な関数が用意されているが、他ファイルのマクロなどを使っている以下の関数を見ていく。その他の関数はちゃんと見てないけど、ぱっと見で特別なところはなさそうか、以下の関数を使って書けるものか、のどちらかっぽい。

  • INIT_LIST_HEAD
  • list_add
  • list_del
  • list_replace
  • list_empty
  • list_del_init_careful
ぷるぷる

INIT_LIST_HEAD

include/linux/list.h
/**
 * INIT_LIST_HEAD - Initialize a list_head structure
 * @list: list_head structure to be initialized.
 *
 * Initializes the list_head to point to itself.  If it is a list header,
 * the result is an empty list.
 */
static inline void INIT_LIST_HEAD(struct list_head *list)
{
	WRITE_ONCE(list->next, list);
	WRITE_ONCE(list->prev, list);
}
include/linux/types.h
struct list_head {
	struct list_head *next, *prev;
};
include/asm-generic/rwonce.h
/*
 * Yes, this permits 64-bit accesses on 32-bit architectures. These will
 * actually be atomic in some cases (namely Armv7 + LPAE), but for others we
 * rely on the access being split into 2x32-bit accesses for a 32-bit quantity
 * (e.g. a virtual address) and a strong prevailing wind.
 */
#define compiletime_assert_rwonce_type(t)					\
	compiletime_assert(__native_word(t) || sizeof(t) == sizeof(long long),	\
		"Unsupported access size for {READ,WRITE}_ONCE().")

...

#define __WRITE_ONCE(x, val)						\
do {									\
	*(volatile typeof(x) *)&(x) = (val);				\
} while (0)

...

#define WRITE_ONCE(x, val)						\
do {									\
	compiletime_assert_rwonce_type(x);				\
	__WRITE_ONCE(x, val);						\
} while (0)
include/linux/compiler_types.h
/* Is this type a native word size -- useful for atomic operations */
#define __native_word(t) \
	(sizeof(t) == sizeof(char) || sizeof(t) == sizeof(short) || \
	 sizeof(t) == sizeof(int) || sizeof(t) == sizeof(long))

#ifdef __OPTIMIZE__
# define __compiletime_assert(condition, msg, prefix, suffix)		\
	do {								\
		/*							\
		 * __noreturn is needed to give the compiler enough	\
		 * information to avoid certain possibly-uninitialized	\
		 * warnings (regardless of the build failing).		\
		 */							\
		__noreturn extern void prefix ## suffix(void)		\
			__compiletime_error(msg);			\
		if (!(condition))					\
			prefix ## suffix();				\
	} while (0)
#else
# define __compiletime_assert(condition, msg, prefix, suffix) do { } while (0)
#endif

#define _compiletime_assert(condition, msg, prefix, suffix) \
	__compiletime_assert(condition, msg, prefix, suffix)

/**
 * compiletime_assert - break build and emit msg if condition is false
 * @condition: a compile-time constant condition to check
 * @msg:       a message to emit if condition is false
 *
 * In tradition of POSIX assert, this macro will break the build if the
 * supplied condition is *false*, emitting the supplied error message if the
 * compiler has support to do so.
 */
#define compiletime_assert(condition, msg) \
	_compiletime_assert(condition, msg, __compiletime_assert_, __COUNTER__)
include/linux/compiler_attributes.h
/*
 * Optional: only supported since clang >= 14.0
 *
 *   gcc: https://gcc.gnu.org/onlinedocs/gcc/Common-Function-Attributes.html#index-error-function-attribute
 */
#if __has_attribute(__error__)
# define __compiletime_error(msg)       __attribute__((__error__(msg)))
#else
# define __compiletime_error(msg)
#endif

...

/*
 *   gcc: https://gcc.gnu.org/onlinedocs/gcc/Common-Function-Attributes.html#index-noreturn-function-attribute
 * clang: https://clang.llvm.org/docs/AttributeReference.html#noreturn
 * clang: https://clang.llvm.org/docs/AttributeReference.html#id1
 */
#define __noreturn                      __attribute__((__noreturn__))

  • 細かいことは置いといて WRITE_ONCE(x, val) は名前からして x = val をするマクロ

  • INIT_LIST_HEAD は1要素の circular doubly linked list を作る関数だとわかる

  • WRITE_ONCE

    • compiletime_assert_rwonce_type
      • 引数の型のサイズが char, short, int, long, long long のいずれとも等しくない場合、READ_ONCE, WRITE_ONCE ができないので assert を入れる
      • compiletime_assert
        • _compiletime_assert
          • これいる?
          • __compiletime_assert
            • do { ... } while (0) の意味
              • ブロックを作り、if のあとにブロックを作らずにマクロを使ったときの意図しない挙動を防ぐ
              • ブロックを作るだけだと、セミコロンをつけたときにエラーになる
            • prefix ## suffix という関数を定義する意味は、コメントで書いてありそうだけどよくわからない
            • __noreturn
            • __compiletime_error
      • __native_word
        • char, short, int, long のいずれかに等しいかを判定
    • __WRITE_ONCE
      • コンパイラによって最適化されないようにした不可分処理?