搜索

[25406] 2016-08-23_Linux内核里的数据结构——位数组

文档创建者：s7ckTeam
浏览次数：1
最后更新：2025-01-19
2016-08-23_Linux内核里的数据结构——位数组 L i n u x   内 核 里 的 数 据 结 构 — — 位 数 组 原 创   译 者 ： c p o s t u r e   L i n u x 中 国   2 0 1 6 - 0 8 - 2 3 L i n u x   内 核 中 的 位 数 组 和 位 操 作 内 核 中 的 位 数 组 和 位 操 作 除 了 不 同 的 基 于 链 式 [ 1 ] 和 树 [ 2 ] 的 数 据 结 构 以 外 ， L i n u x   内 核 也 为 位 数 组 [ 3 ] （ 或 称 为 b i t m a p 位 图 ） 提 供 了   A P I [ 4 ] 。 位 数 组 在   L i n u x   内 核 里 被 广 泛 使 用 ， 并 且 在 以 下 的 源 代 码 文 件 中 包 含 了 与 这 样 的 结 构 搭 配 使 用 的 通 用   ： l i b / b i t m a p . c [ 5 ] i n c l u d e / l i n u x / b i t m a p . h [ 6 ] 除 了 这 两 个 文 件 之 外 ， 还 有 体 系 结 构 特 定 的 头 文 件 ， 它 们 为 特 定 的 体 系 结 构 提 供 优 化 的 位 操 作 。 我 们 将 探 讨   x 8 6 _ 6 4 [ 7 ]   体 系 结 构 ， 因 此 在 我 们 的 例 子 里 ， 它 会 是 a r c h / x 8 6 / i n c l u d e / a s m / b i t o p s . h [ 8 ] 头 文 件 。 正 如 我 上 面 所 写 的 ， 在   L i n u x   内 核 中 被 广 泛 地 使 用 。 例 如 ， 常 常 用 于 保 存 一 组 在 线 / 离 线 处 理 器 ， 以 便 系 统 支 持 热 插 拔 [ 9 ] 的   C P U （ 你 可 以 在   c p u m a s k s [ 1 0 ]   部 分 阅 读 更 多 相 关 知 识   ） ， 一 个 b i t   a r r a y 位 数 组 可 以 在   L i n u x   内 核 初 始 化 等 期 间 保 存 一 组 已 分 配 的 中 断 处 理 [ 1 1 ] 。 因 此 ， 本 部 分 的 主 要 目 的 是 了 解 b i t   a r r a y 位 数 组 是 如 何 在   L i n u x   内 核 中 实 现 的 。 让 我 们 现 在 开 始 吧 。 位 数 组 声 明 位 数 组 声 明 在 我 们 开 始 查 看 操 作 的   A P I 位 图 位 数 组 位 图 A P I
  之 前 ， 我 们 必 须 知 道 如 何 在   L i n u x   内 核 中 声 明 它 。 有 两 种 声 明 位 数 组 的 通 用 方 法 。 第 一 种 简 单 的 声 明 一 个 位 数 组 的 方 法 是 ， 定 义 一 个     的 数 组 ， 例 如 ： 第 二 种 方 法 ， 是 使 用     宏 ， 它 定 义 于   i n c l u d e / l i n u x / t y p e s . h [ 1 2 ]   头 文 件 ： 我 们 可 以 看 到     宏 使 用 两 个 参 数 ：   -   位 图 名 称 ;   -   位 图 中 位 数 ; 并 且 只 是 使 用     元 素 展 开     数 组 的 定 义 。     宏 将 一 个 给 定 的 位 数 转 换 为     的 个 数 ， 换 言 之 ， 就 是 计 算     中 有 多 少 个     字 节 元 素 ： 因 此 ， 例 如   A P I u n s i g n e d   l o n g 1 .   u n s i g n e d   l o n g   m y _ b i t m a p [ 8 ] D E C L A R E _ B I T M A P 1 .   # d e f i n e   D E C L A R E _ B I T M A P ( n a m e , b i t s )   2 .           u n s i g n e d   l o n g   n a m e [ B I T S _ T O _ L O N G S ( b i t s ) ] D E C L A R E _ B I T M A P n a m e b i t s B I T S _ T O _ L O N G S ( b i t s ) u n s i g n e d   l o n g B I T S _ T O _ L O N G S l o n g b i t s 8 1 .   # d e f i n e   B I T S _ P E R _ B Y T E                       8 2 .   # d e f i n e   D I V _ R O U N D _ U P ( n , d )   ( ( ( n )   +   ( d )   -   1 )   /   ( d ) ) 3 .   # d e f i n e   B I T S _ T O _ L O N G S ( n r )               D I V _ R O U N D _ U P ( n r ,   B I T S _ P E R _ B Y T E   *   s i z e o f ( l o n g ) )
  将 产 生 ： 与 ： 在 能 够 声 明 一 个 位 数 组 之 后 ， 我 们 便 可 以 使 用 它 了 。 体 系 结 构 特 定 的 位 操 作 体 系 结 构 特 定 的 位 操 作 我 们 已 经 看 了 上 面 提 及 的 一 对 源 文 件 和 头 文 件 ， 它 们 提 供 了 位 数 组 操 作 的   A P I [ 1 3 ] 。 其 中 重 要 且 广 泛 使 用 的 位 数 组   A P I   是 体 系 结 构 特 定 的 且 位 于 已 提 及 的 头 文 件 中   a r c h / x 8 6 / i n c l u d e / a s m / b i t o p s . h [ 1 4 ] 。 首 先 让 我 们 查 看 两 个 最 重 要 的 函 数 ： ; . 我 认 为 没 有 必 要 解 释 这 些 函 数 的 作 用 。 从 它 们 的 名 字 来 看 ， 这 已 经 很 清 楚 了 。 让 我 们 直 接 查 看 它 们 的 实 现 。 如 果 你 浏 览 a r c h / x 8 6 / i n c l u d e / a s m / b i t o p s . h [ 1 5 ]   头 文 件 ， 你 将 会 注 意 到 这 些 函 数 中 的 每 一 个 都 有 原 子 性 [ 1 6 ] 和 非 原 子 性 两 种 变 体 。 在 我 们 开 始 深 入 这 些 函 数 的 实 现 之 前 ， 首 先 ， 我 们 必 须 了 解 一 些 有 关 a t o m i c 原 子 操 作 的 知 识 。 简 而 言 之 ， 原 子 操 作 保 证 两 个 或 以 上 的 操 作 不 会 并 发 地 执 行 同 一 数 据 。   体 系 结 构 提 供 了 一 系 列 原 子 指 令 ， 例 如 ， x c h g [ 1 7 ] 、 c m p x c h g [ 1 8 ]   等 指 令 。 除 了 原 子 指 令 ， 一 些 非 原 子 指 令 可 以 在   l o c k [ 1 9 ]   指 令 的 帮 助 下 具 有 原 子 性 。 现 在 你 已 经 对 原 子 操 作 有 了 足 够 的 了 解 ， 我 们 可 以 接 着 探 讨     和     函 数 的 实 现 。 我 们 先 考 虑 函 数 的 n o n - a t o m i c 非 原 子 性 变 体 。 非 原 子 性 的     和     的 名 字 以 双 下 划 线 开 始 。 正 如 我 们 所 知 道 的 ， 所 有 这 些 函 数 都 定 义 于   a r c h / x 8 6 / i n c l u d e / a s m / b i t o p s . h [ 2 0 ]   头 文 件 ， 并 且 第 一 个 函 数 就 是   : D E C L A R E _ B I T M A P ( m y _ b i t m a p ,   6 4 ) 1 .   > > >   ( ( ( 6 4 )   +   ( 6 4 )   -   1 )   /   ( 6 4 ) ) 2 .   1 1 .   u n s i g n e d   l o n g   m y _ b i t m a p [ 1 ] ; s e t _ b i t c l e a r _ b i t x 8 6 s e t _ b i t c l e a r _ b i t s e t _ b i t c l e a r _ b i t _ _ s e t _ b i t
正 如 我 们 所 看 到 的 ， 它 使 用 了 两 个 参 数 ：   -   位 数 组 中 的 位 号 （ L C T T   译 注 ： 从   0   开 始 ）   -   我 们 需 要 置 位 的 位 数 组 地 址 注 意 ，   参 数 使 用     关 键 字 定 义 ， 以 告 诉 编 译 器 给 定 地 址 指 向 的 变 量 可 能 会 被 修 改 。     的 实 现 相 当 简 单 。 正 如 我 们 所 看 到 的 ， 它 仅 包 含 一 行 内 联 汇 编 代 码 [ 2 1 ] 。 在 我 们 的 例 子 中 ， 我 们 使 用   b t s [ 2 2 ]   指 令 ， 从 位 数 组 中 选 出 一 个 第 一 操 作 数 （ 我 们 的 例 子 中 的   ） 所 指 定 的 位 ， 存 储 选 出 的 位 的 值 到   C F [ 2 3 ]   标 志 寄 存 器 并 设 置 该 位 （ L C T T   译 注 ： 即     指 定 的 位 置 为   1 ） 。 注 意 ， 我 们 了 解 了     的 用 法 ， 但 这 里 还 有 一 个 参 数     呢 ！ 你 或 许 已 经 猜 到 秘 密 就 在   。     是 一 个 定 义 在 同 一 个 头 文 件 中 的 宏 ， 它 展 开 为 一 个 包 含 给 定 地 址 和     约 束 的 字 符 串 ： 除 了   1 .   s t a t i c   i n l i n e   v o i d   _ _ s e t _ b i t ( l o n g   n r ,   v o l a t i l e   u n s i g n e d   l o n g   * a d d r ) 2 .   { 3 .           a s m   v o l a t i l e ( " b t s   % 1 , % 0 "   :   A D D R   :   " I r "   ( n r )   :   " m e m o r y " ) ; 4 .   } n r a d d r a d d r v o l a t i l e _ _ s e t _ b i t n r n r n r a d d r A D D R A D D R + m 1 .   # d e f i n e   A D D R                                 B I T O P _ A D D R ( a d d r ) 2 .   # d e f i n e   B I T O P _ A D D R ( x )   " + m "   ( * ( v o l a t i l e   l o n g   * )   ( x ) ) + m
  之 外 ， 在     函 数 中 我 们 可 以 看 到 其 他 约 束 。 让 我 们 查 看 并 试 着 理 解 它 们 所 表 示 的 意 义 ：   -   表 示 内 存 操 作 数 ， 这 里 的     表 明 给 定 的 操 作 数 为 输 入 输 出 操 作 数 ；   -   表 示 整 型 常 量 ；   -   表 示 寄 存 器 操 作 数 除 了 这 些 约 束 之 外 ， 我 们 也 能 看 到     关 键 字 ， 其 告 诉 编 译 器 这 段 代 码 会 修 改 内 存 中 的 变 量 。 到 此 为 止 ， 现 在 我 们 看 看 相 同 的 a t o m i c 原 子 性 变 体 函 数 。 它 看 起 来 比 n o n - a t o m i c 非 原 子 性 变 体 更 加 复 杂 ： （ L C T T   译 注 ： B I T O P _ A D D R   的 定 义 为 ： ， O R B   为 字 节 按 位 或 。 ） 首 先 注 意 ， 这 个 函 数 使 用 了 与     相 同 的 参 数 集 合 ， 但 额 外 地 使 用 了   _ _ s e t _ b i t + m + I r m e m o r y 1 .   s t a t i c   _ _ a l w a y s _ i n l i n e   v o i d 2 .   s e t _ b i t ( l o n g   n r ,   v o l a t i l e   u n s i g n e d   l o n g   * a d d r ) 3 .   { 4 .           i f   ( I S _ I M M E D I A T E ( n r ) )   { 5 .                   a s m   v o l a t i l e ( L O C K _ P R E F I X   " o r b   % 1 , % 0 " 6 .                           :   C O N S T _ M A S K _ A D D R ( n r ,   a d d r ) 7 .                           :   " i q "   ( ( u 8 ) C O N S T _ M A S K ( n r ) ) 8 .                           :   " m e m o r y " ) ; 9 .           }   e l s e   { 1 0 .                   a s m   v o l a t i l e ( L O C K _ P R E F I X   " b t s   % 1 , % 0 " 1 1 .                           :   B I T O P _ A D D R ( a d d r )   :   " I r "   ( n r )   :   " m e m o r y " ) ; 1 2 .           } 1 3 .   } # d e f i n e   B I T O P _ A D D R ( x )   " = m "   ( * ( v o l a t i l e   l o n g   * )   ( x ) ) _ _ s e t _ b i t _ _ a l w a y s _ i n l i n e
  属 性 标 记 。   是 一 个 定 义 于   i n c l u d e / l i n u x / c o m p i l e r - g c c . h [ 2 4 ]   的 宏 ， 并 且 只 是 展 开 为     属 性 ： 其 意 味 着 这 个 函 数 总 是 内 联 的 ， 以 减 少   L i n u x   内 核 映 像 的 大 小 。 现 在 让 我 们 试 着 了 解 下     函 数 的 实 现 。 首 先 我 们 在     函 数 的 开 头 检 查 给 定 的 位 的 数 量 。   宏 定 义 于 相 同 的 头 文 件 [ 2 5 ] ， 并 展 开 为   g c c [ 2 6 ]   内 置 函 数 的 调 用 ： 如 果 给 定 的 参 数 是 编 译 期 已 知 的 常 量 ，   内 置 函 数 则 返 回   ， 其 他 情 况 返 回   。 假 若 给 定 的 位 数 是 编 译 期 已 知 的 常 量 ， 我 们 便 无 须 使 用 效 率 低 下 的     指 令 去 设 置 位 。 我 们 可 以 只 需 在 给 定 地 址 指 向 的 字 节 上 执 行   按 位 或 [ 2 7 ]   操 作 ， 其 字 节 包 含 给 定 的 位 ， 掩 码 位 数 表 示 高 位 为   ， 其 他 位 为   0   的 掩 码 。 在 其 他 情 况 下 ， 如 果 给 定 的 位 号 不 是 编 译 期 已 知 常 量 ， 我 们 便 做 和     函 数 一 样 的 事 。   宏 ： 展 开 为 带 有 到 包 含 给 定 位 的 字 节 偏 移 的 给 定 地 址 ， 例 如 ， 我 们 拥 有 地 址     和 位 号   。 因 为   _ _ a l w a y s _ i n l i n e a l w a y s _ i n l i n e 1 .   # d e f i n e   _ _ a l w a y s _ i n l i n e   i n l i n e   _ _ a t t r i b u t e _ _ ( ( a l w a y s _ i n l i n e ) ) s e t _ b i t s e t _ b i t I S _ I M M E D I A T E 1 .   # d e f i n e   I S _ I M M E D I A T E ( n r )                 ( _ _ b u i l t i n _ c o n s t a n t _ p ( n r ) ) _ _ b u i l t i n _ c o n s t a n t _ p 1 0 b t s 1 _ _ s e t _ b i t C O N S T _ M A S K _ A D D R 1 .   # d e f i n e   C O N S T _ M A S K _ A D D R ( n r ,   a d d r )       B I T O P _ A D D R ( ( v o i d   * ) ( a d d r )   +   ( ( n r ) > > 3 ) ) 0 x 1 0 0 0 0 x 9 0 x 9
  代 表   ， 所 以 我 们 的 地 址 是   :   宏 将 我 们 给 定 的 位 号 表 示 为 字 节 ， 位 号 对 应 位 为 高 位   ， 其 他 位 为   ： 最 后 ， 我 们 应 用     运 算 到 这 些 变 量 上 面 ， 因 此 ， 假 如 我 们 的 地 址 是     ， 并 且 我 们 需 要 置 位 号 为     的 位 为   1 ：   将 会 被 置 位 。 （ L C T T   译 注 ： 这 里 的   9   是 从   0   开 始 计 数 的 ， 比 如 0 0 1 0 ， 按 照 作 者 的 意 思 ， 其 中 的   1   是 第   1   位 ） 注 意 ， 所 有 这 些 操 作 使 用   一 个 字 节   +   一 位 a d d r   +   1 1 .   > > >   h e x ( 0 x 1 0 0 0   +   ( 0 x 9   > >   3 ) ) 2 .   ' 0 x 1 0 0 1 ' C O N S T _ M A S K 1 0 1 .   # d e f i n e   C O N S T _ M A S K ( n r )                     ( 1   < <   ( ( n r )   &   7 ) ) 1 .   > > >   b i n ( 1   < <   ( 0 x 9   &   7 ) ) 2 .   ' 0 b 1 0 ' 按 位 或 0 x 4 0 9 7 9 1 .   > > >   b i n ( 0 x 4 0 9 7 ) 2 .   ' 0 b 1 0 0 0 0 0 0 1 0 0 1 0 1 1 1 ' 3 .   > > >   b i n ( ( 0 x 4 0 9 7   > >   0 x 9 )   |   ( 1   < <   ( 0 x 9   &   7 ) ) ) 4 .   ' 0 b 1 0 0 0 1 0 ' 第   9   位
  标 记 ， 其 展 开 为   l o c k [ 2 8 ]   指 令 ， 保 证 该 操 作 的 原 子 性 。 正 如 我 们 所 知 ， 除 了     和     操 作 之 外 ， L i n u x   内 核 还 提 供 了 两 个 功 能 相 反 的 函 数 ， 在 原 子 性 和 非 原 子 性 的 上 下 文 中 清 位 。 它 们 是     和   。 这 两 个 函 数 都 定 义 于 同 一 个 头 文 件 [ 2 9 ]   并 且 使 用 相 同 的 参 数 集 合 。 不 仅 参 数 相 似 ， 一 般 而 言 ， 这 些 函 数 与     和     也 非 常 相 似 。 让 我 们 查 看 非 原 子 性   的 实 现 吧 ： 没 错 ， 正 如 我 们 所 见 ，   使 用 相 同 的 参 数 集 合 ， 并 包 含 极 其 相 似 的 内 联 汇 编 代 码 块 。 它 只 是 使 用   b t r [ 3 0 ]   指 令 替 换 了   。 正 如 我 们 从 函 数 名 所 理 解 的 一 样 ， 通 过 给 定 地 址 ， 它 清 除 了 给 定 的 位 。   指 令 表 现 得 像 （ L C T T   译 注 ： 原 文 这 里 为   b t r ， 可 能 为 笔 误 ， 修 正 为   b t s ） 。 该 指 令 选 出 第 一 操 作 数 所 指 定 的 位 ， 存 储 它 的 值 到   标 志 寄 存 器 ， 并 且 清 除 第 二 操 作 数 指 定 的 位 数 组 中 的 对 应 位 。   的 原 子 性 变 体 为   ： L O C K _ P R E F I X s e t _ b i t _ _ s e t _ b i t c l e a r _ b i t _ _ c l e a r _ b i t s e t _ b i t _ _ s e t _ b i t _ _ c l e a r _ b i t 1 .   s t a t i c   i n l i n e   v o i d   _ _ c l e a r _ b i t ( l o n g   n r ,   v o l a t i l e   u n s i g n e d   l o n g   * a d d r ) 2 .   { 3 .           a s m   v o l a t i l e ( " b t r   % 1 , % 0 "   :   A D D R   :   " I r "   ( n r ) ) ; 4 .   } _ _ c l e a r _ b i t b t s b t r b t s C F _ _ c l e a r _ b i t c l e a r _ b i t 1 .   s t a t i c   _ _ a l w a y s _ i n l i n e   v o i d 2 .   c l e a r _ b i t ( l o n g   n r ,   v o l a t i l e   u n s i g n e d   l o n g   * a d d r ) 3 .   {
并 且 正 如 我 们 所 看 到 的 ， 它 与     非 常 相 似 ， 只 有 两 处 不 同 。 第 一 处 差 异 为     使 用     指 令 来 清 位 ， 而     使 用     指 令 来 置 位 。 第 二 处 差 异 为     使 用 否 定 的 位 掩 码 和     在 给 定 的 字 节 上 置 位 ， 而     使 用     指 令 。 到 此 为 止 ， 我 们 可 以 在 任 意 位 数 组 置 位 和 清 位 了 ， 我 们 将 看 看 位 掩 码 上 的 其 他 操 作 。 在   L i n u x   内 核 中 对 位 数 组 最 广 泛 使 用 的 操 作 是 设 置 和 清 除 位 ， 但 是 除 了 这 两 个 操 作 外 ， 位 数 组 上 其 他 操 作 也 是 非 常 有 用 的 。 L i n u x   内 核 里 另 一 种 广 泛 使 用 的 操 作 是 知 晓 位 数 组 中 一 个 给 定 的 位 是 否 被 置 位 。 我 们 能 够 通 过     宏 的 帮 助 实 现 这 一 功 能 。 这 个 宏 定 义 于   a r c h / x 8 6 / i n c l u d e / a s m / b i t o p s . h [ 3 1 ]   头 文 件 ， 并 根 据 位 号 分 别 展 开 为   或     调 用 。 3 .   { 4 .           i f   ( I S _ I M M E D I A T E ( n r ) )   { 5 .                   a s m   v o l a t i l e ( L O C K _ P R E F I X   " a n d b   % 1 , % 0 " 6 .                           :   C O N S T _ M A S K _ A D D R ( n r ,   a d d r ) 7 .                           :   " i q "   ( ( u 8 ) ~ C O N S T _ M A S K ( n r ) ) ) ; 8 .           }   e l s e   { 9 .                   a s m   v o l a t i l e ( L O C K _ P R E F I X   " b t r   % 1 , % 0 " 1 0 .                           :   B I T O P _ A D D R ( a d d r ) 1 1 .                           :   " I r "   ( n r ) ) ; 1 2 .           } 1 3 .   } s e t _ b i t c l e a r _ b i t b t r s e t _ b i t b t s c l e a r _ b i t 按 位 与 s e t _ b i t 按 位 或 t e s t _ b i t c o n s t a n t _ t e s t _ b i t v a r i a b l e _ t e s t _ b i t
因 此 ， 如 果     是 编 译 期 已 知 常 量 ，   将 展 开 为     函 数 的 调 用 ， 而 其 他 情 况 则 为 。 现 在 让 我 们 看 看 这 些 函 数 的 实 现 ， 让 我 们 从     开 始 看 起 ： 4 .   9 .     函 数 使 用 了 与     及 其 他 函 数 使 用 的 相 似 的 参 数 集 合 。 我 们 也 可 以 看 到 执 行   b t [ 3 2 ]   和 s b b [ 3 3 ]   指 令 的 内 联 汇 编 代 码 。   （ 或 称   1 .   # d e f i n e   t e s t _ b i t ( n r ,   a d d r )                     2 .           ( _ _ b u i l t i n _ c o n s t a n t _ p ( ( n r ) )                                   3 .             ?   c o n s t a n t _ t e s t _ b i t ( ( n r ) ,   ( a d d r ) )                     4 .             :   v a r i a b l e _ t e s t _ b i t ( ( n r ) ,   ( a d d r ) ) ) n r t e s t _ b i t c o n s t a n t _ t e s t _ b i t v a r i a b l e _ t e s t _ b i t v a r i a b l e _ t e s t _ b i t 1 .   s t a t i c   i n l i n e   i n t   v a r i a b l e _ t e s t _ b i t ( l o n g   n r ,   v o l a t i l e   c o n s t   u n s i g n e d   l o n g   * a d d r ) 2 .   { 3 .           i n t   o l d b i t ; 5 .           a s m   v o l a t i l e ( " b t   % 2 , % 1 n t " 6 .                             " s b b   % 0 , % 0 " 7 .                             :   " = r "   ( o l d b i t ) 8 .                             :   " m "   ( * ( u n s i g n e d   l o n g   * ) a d d r ) ,   " I r "   ( n r ) ) ; 1 0 .           r e t u r n   o l d b i t ; 1 1 .   } v a r i a b l e _ t e s t _ b i t s e t _ b i t b t b i t   t e s t
回复

举报

高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

使用Markdown编辑器编辑 使用富文本编辑器编辑

Archiver| 手机版| 小黑屋|
Powered by Discuz! X3.4 Copyright © 2001-2020, Tencent Cloud. 商业源码建议获取授权，如侵犯您的权益，请联系客服处理