プロンプトとコンテキスト
カーネルサブシステムは、検索、挿入、削除、ギャップ反復を伴う、重複しない多数の整数範囲を管理する必要があります。Maple Treeの構造、並行アクセス、アロケーション制約、および古い構造からの移行をどのように検証するかを説明してください。
Linuxカーネルのドキュメントでは、Maple Treeは重複しない範囲向けに最適化されたB-treeとして説明されています。ポイントインデックスと範囲を格納し、通常のアロケーションモードと制約付きアロケーションモードをサポートし、自身のロック下またはRCUを使用して読み取ることができます。この面接では、単に「赤黒木よりも高速である」という主張ではなく、ライフサイクル、ロック、アロケーションのセマンティクスが試されます。
面接官が評価するポイント
面接官は、インデックス値、範囲値、ギャップの区別、ノードの分割・マージ・操作状態の説明、GFP、ロック、参照カウント、RCUの適切な処理、移行時における非重複性、反復順序、削除セマンティクスの維持、並行性やメモリ圧迫を含むベンチマークを評価します。
明確化のための質問
範囲モデル
範囲が閉区間であるか、終端が最大整数になり得るか、隣接する範囲がマージされるか、ギャップに意味があるか、1つのインデックスが1つのオブジェクトにマップされるかを確認します。
並行性とコンテキスト
呼び出し元がプロセスコンテキスト、割り込みコンテキスト、スリープ不可（non-sleepable）コンテキストのいずれで実行されるか、リーダーがRCUを使用できるか、ライターがMaple Treeの内部ロックまたは外部ロックのどちらに依存するかを確認します。
移行対象
互換性を維持する必要がある古い構造の複雑さ、メモリ予算、安定したABI、デバッグツール、エラーコードを確認します。移行の成否はシングルスレッドのスループットだけで判断することはできません。
30秒の回答
「Maple Treeは範囲指向のB-treeノードを使用してインデックスと区間をパックするため、重複しない範囲やギャップのクエリに適しています。通常の更新ではGFPルールに従ってアロケーションが行われる場合がありますが、アトミックパスやスリープ不可パスでは準備された操作状態と制約付きアロケーションが必要です。リーダーはロックを使用するか、RCU下では読み取りセクションを抜ける前にオブジェクト参照を取得します。不変条件と二重書き込みによる比較を確立し、境界、ギャップ、削除、並行性、メモリ圧迫をテストした上で、実ワークロードのレイテンシとフットプリントを比較します。」
ステップバイステップの解決策
ステップ 1: 範囲の不変条件を定義する
各エントリの開始インデックスと終了インデックス、空の値が許可されるかどうか、隣接する範囲がマージされるかどうかを指定します。すべての挿入、置換、削除は、終端のオーバーフローや空の範囲に対する明示的な動作を伴い、非重複性を維持する必要があります。
ステップ 2: ノードと操作状態を理解する
Maple Treeノードは複数のピボットとスロットを格納し、ポインタの深さを減らして範囲の局所性を向上させます。複雑な反復や更新では、現在の位置と操作コンテキストのためにma_stateを使用できます。サポートされていない並行境界を越えて状態を再利用しないでください。
ステップ 3: アロケーションモードを選択する
通常の更新ではGFP_KERNELを使用してアロケーションを行い、スリープする可能性があります。スリープ不可パスでは、事前アロケーションまたは制約付きGFPフラグ、および準備された操作状態が必要です。スピンロックを保持している間やRCU読み取りセクション内で、スリープする可能性のあるアロケーションパスを決して呼び出さないでください。
ステップ 4: 読み取りの一貫性を設計する
ロックベースの読み取りはシンプルです。RCUを使用する場合は、RCUセクションを抜ける前に参照を取得するか、必要なデータをコピーします。オブジェクトの解放は、参照カウント、コールバック、ツリーからの削除を一致させる必要があります。ノード単体を保護しても、値のライフタイムは保護されません。
ステップ 5: 範囲とギャップの検索を実装する
インデックスでの検索は、カバーする範囲または値を返さない状態を返します。ギャップの反復は前のエントリの末尾から継続するため、最初と最後の境界がスキップされることはありません。イテレータは次のインデックスを記録し、並行削除や最大インデックスを処理します。「値なし」が自動的に反復の終了を意味するわけではありません。
lookup(index):
lock_or_rcu_read()
entry = maple_lookup(index)
if entry != null:
refcount_inc(entry.owner)
unlock_or_rcu_read()
return entry
find_gap(start, end):
state = maple_state(start)
while state.index <= end:
range = maple_next_range(state)
if gap_before(range, state.index): return [state.index, range.start - 1]
state.index = range.end + 1
return [state.index, end]ステップ 6: 古い構造を移行する
二重書き込みやサイドインデックスを構築している間は、古い構造を信頼できる情報源（source of truth）として維持します。ランダムな境界、重複する挿入、削除後のギャップ、並行読み取りを比較します。エラーコード、ロック順序、アロケーション失敗、リカバリ動作が一致した後にのみ、読み取りパスを切り替えます。
ステップ 7: 改善点とロールバックを検証する
検索、範囲反復、ギャップ検索、更新のレイテンシパーセンタイルを、ノードメモリ、アロケーション失敗、ロック待ちとともに記録します。フィーチャースイッチと一貫性カウンターを維持し、本番ワークロードテストを単一のマイクロベンチマークで置き換えるのではなく、不一致が発生した場合は停止してロールバックします。
模範解答
まず非重複、終端、ギャップの不変条件を定義し、次にMaple Treeの範囲指向B-treeに範囲を格納します。スリープ可能な通常パスではGFP_KERNELを使用できます。スリープ不可パスでは状態を準備し、ロックやRCUセクション内でのアロケーションを回避します。リーダーはロックを保持するか、RCU下でオブジェクトを使用する前に参照を取得し、参照カウントによって値のライフタイムを保護します。移行中は二重書き込みを行い、検索、ギャップ、削除、境界の動作を比較し、古い実装をロールバックパスとして維持しながら、レイテンシ、メモリ、アロケーション失敗のメトリクスを使用して切り替えます。
よくある間違い
- 間違い: Maple Treeをポイントキーのマップとして扱う。 → なぜ失敗するか: その価値は重複しない範囲とギャップ操作にあります。 → 修正方法: 終端、カバー検索、ギャップ反復を定義する。
- 間違い: スピンロック下またはRCU読み取りセクション内でスリープする可能性のある更新を呼び出す。 → なぜ失敗するか: GFPアロケーションコンテキストはそのような場所でスリープできません。 → 修正方法: 事前アロケーションを行い、正しいモードを選択し、ロック境界を分離する。
- 間違い: 値オブジェクトではなく、ツリーノードのみを保護する。 → なぜ失敗するか: ロック解除後に値が解放される可能性があります。 → 修正方法: RCUまたはロックセクションを抜ける前に、コピーするか参照を取得する。
- 間違い: 移行中に検索スループットのみを測定する。 → なぜ失敗するか: 分割、削除、ギャップ、メモリ圧迫が支配的になる可能性があります。 → 修正方法: 現実的な範囲、並行性、アロケーション失敗のシナリオを比較する。
フォローアップと回答
Maple Treeか赤黒木か？
単純な順序付きポイントキーの場合、赤黒木で十分な場合があります。重複しない範囲の大規模なセット、ギャップクエリ、および局所性にはMaple Treeが適しています。ワークロードと並行性のメトリクスに基づいて決定してください。
どのような場合にRCUを使用しますか？
値が猶予期間（grace period）の後に安全に回収できる場合で、ロック競合が少ない読み取り頻度の高いパスに使用します。リーダーがオブジェクトを即座に変更する必要がある場合や、参照を管理できない場合は、ロックベースのアクセスのほうが明確です。
mtree_erase()がGFP_KERNELを必要とする場合があるのはなぜですか？
削除によってノードの再構築や関連するアロケーション作業がトリガーされる可能性があるため、呼び出し元のコンテキストで必要なメモリオペレーションが許可されている必要があります。スリープ不可パスには、ドキュメントに記載されている制約付きインターフェースと準備された状態が必要です。
ギャップがスキップされていないことをどのように証明しますか？
網羅的な境界、隣接する範囲、最大インデックス、ランダムな削除を含む正確なモデルを生成し、並行削除やイテレータの再起動を含め、すべてのギャップの終端を比較します。