头条消息

LinuxCon Japan 2016 和 ContainerCon Japan 2016 即将在 7 月 13 日 – 15 日于日本东京召开。Linus Torvalds 会出席。

期待已久的 Ubuntu 手机和平板设备上的 OTA-11 更新指日可待。这个版本中最期待功能可能是支持 Aethercast 技术的无线显示技术,也就是说,Ubuntu 手机/平板可以不用线缆连接到显示器即可使用桌面显示器了(这个功能支持所有的设备,除了使用自己的无线显示技术的魅族 PRO 5)。其次,这个更新中会使用网络管理器 1.2,其 MAC 地址随机技术可以避免手机在 Wi-Fi 环境中被跟踪。另外,它的Web 浏览器改善了各个厂商设备上的 Google Hangouts 用户体验,还会降低了后台运行的选项卡的内存占用。

版本更迭

  • 基于 Firefox 45-ESR 的 Tor Browser 6.0 发布,修复了一些安全问题,同时提供了对 HTML5 更好支持。值得一提的是,Tor Browser 6.0 告别了 SHA-1 证书,提供了更好的更新机制。现在可以下载使用咯。
  • 基于 CentOS 7 Linux 的 Koozali SME Server 10 操作系统第一个 Alpha 版本发布。SME Server 是为各种中小型企业设计的 GNU/Linux 发行版。
  • Mesa 12.0.0 3D 宣布开始进行开发,第一个发行候选版本可以下载测试了。
  • 基于 Ubuntu 16.04 LTS 的 ExTiX 16.3 LXQt 发布,搭载了 Linux 4.6 内核,采用了轻量级的 LXQt 0.10.0 桌面环境,使用 Google Chrome 作为默认浏览器。

随着 Ubuntu 16.04 LTS 的发布,Ubuntu 的软件包管理命令也发生了变化,新系统采用了 Debian 项目中所使用的 APT(Advanced Package Tool)来完成各种的不同的任务,APT 命令全面取代了我们之前在 Linux 软件包管理基本操作入门中所介绍的 apt-get、apt-cache 等功能。

APT 在创建之初便是为了解决大量软件包管理所遇到的问题,希望结束类似 Linux 早期系统依赖的一大弊病。不过 APT 命令本身的文档较为分散,刚上手的用户很难找到它的帮助信息。

过去十多年以来,几乎所有 Debian 和 Ubuntu 用户都在使用 apt-get 进行安装、删除软件包等管理操作。现在大家也应该试着切换到新的 APT 命令来了。

注意:为兼顾老用户的使用习惯 Ubuntu 16.04 依然保留着 apt-get 系列命令。

使用APT简化命令行

下面我们列出 Ubuntu 16.04 LTS 中使用 ATP 命令与老版本 Ubuntu 中软件包管理的用法对比:

Ubuntu 16.04 LTS 老版本Ubuntu
apt install 包名 替代 apt-get install 包名
apt remove 包名 替代 apt-get remove 包名
apt search 包名 替代 apt-cache search 包名
apt show 包名 替代 apt-cache show 包名
apt update 替代 apt-get update
apt upgrade 替代 apt-get upgrade
apt list –installed
  • 替代 dpkg –get-selections | grep -v deinstall
  • 替代 dpkg -l
apt list –upgradable apt-get -u upgrade –assume-no
apt edit-sources
  • 替代 echo ‘new line of text’ | sudo tee -a /etc/apt/sources.list
  • 替代 sudo nano /etc/apt/sources.list
apt autoremove 替代 apt-get autoremove
apt purge 包名 替代 apt-get purge 包名

有一天,我回复了 Facebook 上的一个帖子,说我预测未来五年内,各大平台都将成为开放平台,其中我提到了 Windows 和 OS X。

微软和苹果都已经为开源产品得到接受奠定了框架。苹果甚至有一个开源网页显示了它在2015年已经开放的所有产品;微软更是公开表示,“开源 Windows 绝对有可能”。如果你考虑一下企业计算界的状态,就会清楚地发现,不开源的产品处境正岌岌可危。

不祥之兆已经出现在眼前……开源已获胜,运行着世界上一些最强大的网络和系统。如果各大软件厂商想在这个市场分得一杯羹,就得玩开放这个游戏。

此外,微软和苹果都无法再从操作系统赚得大把大把的钱。两家公司甚至免费派送主要版本的升级版。以平台来获利的商业模式已听到丧钟在敲响。

不过等等……难不成 Linux 爱好者要向闭源软件敞开怀抱?是这样的。

容我细细道来。

混合起来

我经常使用的软件大多是开源软件。LibreOffice、GIMP、Audacity、OpenShot、Thunderbird、Clementine……这些是我每天都在使用的开源应用程序。然而,也有几款应用程序是闭源软件。Chrome、Spotify 客户软件、Google Apps 和Insync……它们都是闭源。然而,所有这些软件都可以在完全是开源产品的 Elementary OS Freya 上运行。所以,我平时使用的是开源软件和闭源软件的混合体。

很多人会告诉我,我可以把那些少数几款闭源软件换成开放软件。Chromium 可以处理 Chrome 的任务,Grive2 可以取代Insync,Spotify Web 客户软件效果很好,几款软件的组合体也可以取代 Google Apps。

当然,这完全有可能。然而,我需要的是能够高效、可靠地工作。我乐于放弃那些闭源软件,换成开源软件,要是有相应开源软件的话。没错,Chromium 应该可以临时替代 Chrome,但是我不止一次地发现,Chromium 和 Google Apps 并不总是相处得很好。

说实话,有些应用程序是我不可或缺的,而它们恰好又是闭源软件。由于那些闭源应用程序可以在 Linux 上运行,我的日常任务处理起来很顺畅。要是那些应用程序在 Linux 生态系统里面无法正常使用,我也就懒得使用了。问题是,它们可以正常使用。正由于如此,我才使用它们。正由于我(及其他许多人)使用它们,它们才会存在。

理想很美好

要是每一个软件都是开源软件,那就太好了。试想一下种种可能。天空不再是极限。然而,这一幕不会发生。虽然我们很可能生活在各大平台都是开放平台的世界,但是并不代表位于操作系统之上全都是开放的。有些公司仍需要盈利才能走开放之道,他们完全相信,如果开源核心产品,就不可能盈利。这些公司可不是微软或苹果(它们可以依赖来自硬件或服务的利润),所以那些应用程序是它们赖以为生的产品。

正由于如此,又由于像微软和苹果这些公司已清醒地认识到了现实(“平台”想保持其重要性,唯一的出路就是开放),开源拥趸是时候敞怀拥抱闭源应用程序了。然而这绝不意味着你对自由这个理念不抱有希望。而是说,最适合某项任务的工具才是你应该使用的工具,无论是开源、闭源,还是两者的结合体。如果你对闭源工具不予考虑,有可能错失一些非常出色的应用程序。除此之外,你在开源环境上使用闭源应用程序越多,可供使用的软件就会越多。这就是我所说的“反向的梦想之地”。

有人买它们,才有人开发它们。

最近我一直越来越多地看到这一幕。一款新的软件会引起我的注意,如果我打量一下,就会发现他们为所有平台(包括 Linux)开发其工具。这么做的重要性不容忽视。想想看,许多公司在发布面向 Linux 的源代码,我们不必请愿、发邮件或恳请。我的朋友们,这是时代的标志。也许他们没有发布源代码,但是应用程序可以在我们选择的平台上运行。现在,针对闭源软件的战斗口号可以偃旗息鼓了。

开源已经为我服务了十多年,我从来没有想要使用闭源的桌面或服务器平台。原因何在?因为我发觉 Linux 对我来说就是最好的一种平台,可以高效、可靠地完成工作。然而,我会在那些平台上使用可以完成工作的任何工具。闭源工具、开源工具或两者的结合体,都会使用。如果市面上出现了闭源应用程序的切实可行的开源替代版本,我很乐意换掉那个闭源软件。不过在此之前,你也明白我的意思,我会继续使用闭源软件。

基数树Radix tree

Trie

正如你所知道的,Linux内核提供了许多不同的库和函数,它们实现了不同的数据结构和算法。在这部分,我们将研究其中一种数据结构——基数树Radix tree。在 Linux 内核中,有两个文件与基数树的实现和API相关:

让我们先说说什么是 基数树 吧。基数树是一种 压缩的字典树 compressed trie ,而字典树是实现了关联数组接口并允许以 键值对 方式存储值的一种数据结构。这里的键通常是字符串,但可以使用任意数据类型。字典树因为它的节点而与 n叉树 不同。字典树的节点不存储键,而是存储单个字符的标签。与一个给定节点关联的键可以通过从根遍历到该节点获得。举个例子:

               +-----------+
               |           |
               |    " "    |
               |           |
        +------+-----------+------+
        |                         |
        |                         |
   +----v------+            +-----v-----+
   |           |            |           |
   |    g      |            |     c     |
   |           |            |           |
   +-----------+            +-----------+
        |                         |
        |                         |
   +----v------+            +-----v-----+
   |           |            |           |
   |    o      |            |     a     |
   |           |            |           |
   +-----------+            +-----------+
                                  |
                                  |
                            +-----v-----+
                            |           |
                            |     t     |
                            |           |
                            +-----------+

因此在这个例子中,我们可以看到一个有着两个键 gocat字典树 。压缩的字典树也叫做 基数树 ,它和 字典树 的不同之处在于,所有只有一个子节点的中间节点都被删除。

Linux 内核中的基数树是把值映射到整形键的一种数据结构。include/linux/radix-tree.h文件中的以下结构体描述了基数树:

struct radix_tree_root {
         unsigned int            height;
         gfp_t                   gfp_mask;
         struct radix_tree_node  __rcu *rnode;
};

这个结构体描述了一个基数树的根,它包含了3个域成员:

  • height – 树的高度;
  • gfp_mask – 告知如何执行动态内存分配;
  • rnode – 孩子节点指针.

我们第一个要讨论的字段是 gfp_mask

底层内核的内存动态分配函数以一组标志作为 gfp_mask ,用于描述如何执行动态内存分配。这些控制分配进程的 GFP_ 标志拥有以下值:( GF_NOIO 标志)意味着睡眠以及等待内存,( __GFP_HIGHMEM 标志)意味着高端内存能够被使用,( GFP_ATOMIC 标志)意味着分配进程拥有高优先级并不能睡眠等等。

  • GFP_NOIO – 睡眠等待内存
  • __GFP_HIGHMEM – 高端内存能够被使用;
  • GFP_ATOMIC – 分配进程拥有高优先级并且不能睡眠;

等等。

下一个字段是rnode

struct radix_tree_node {
        unsigned int    path;
        unsigned int    count;
        union {
                struct {
                        struct radix_tree_node *parent;
                        void *private_data;
                };
                struct rcu_head rcu_head;
        };
        /* For tree user */
        struct list_head private_list;
        void __rcu      *slots[RADIX_TREE_MAP_SIZE];
        unsigned long   tags[RADIX_TREE_MAX_TAGS][RADIX_TREE_TAG_LONGS];
};

这个结构体包含的信息有父节点中的偏移以及到底端(叶节点)的高度、子节点的个数以及用于访问和释放节点的字段成员。这些字段成员描述如下:

  • path – 父节点中的偏移和到底端(叶节点)的高度
  • count – 子节点的个数;
  • parent – 父节点指针;
  • private_data – 由树的用户使用;
  • rcu_head – 用于释放节点;
  • private_list – 由树的用户使用;

radix_tree_node 的最后两个成员—— tagsslots 非常重要且令人关注。Linux 内核基数树的每个节点都包含了一组指针槽 slots ,槽里存储着指向数据的指针。在Linux内核基数树的实现中,空槽存储的是 NULL 。Linux内核中的基数树也支持标签 tags ,它与 radix_tree_node 结构体的 tags 字段相关联。有了标签,我们就可以对基数树中存储的记录以单个比特位 bit 进行设置。

既然我们了解了基数树的结构,那么该是时候看一下它的API了。

Linux内核基数树API

我们从结构体的初始化开始。有两种方法初始化一个新的基数树。第一种是使用 RADIX_TREE 宏:

RADIX_TREE(name, gfp_mask);

正如你所看到的,我们传递了 name 参数,所以通过 RADIX_TREE 宏,我们能够定义和初始化基数树为给定的名字。RADIX_TREE 的实现很简单:

#define RADIX_TREE(name, mask) /
         struct radix_tree_root name = RADIX_TREE_INIT(mask)

#define RADIX_TREE_INIT(mask)   { /
        .height = 0,              /
        .gfp_mask = (mask),       /
        .rnode = NULL,            /
}

RADIX_TREE 宏的开始,我们使用给定的名字定义 radix_tree_root 结构体实例,并使用给定的 mask 调用 RADIX_TREE_INIT 宏。 而 RADIX_TREE_INIT 宏则是使用默认值和给定的mask对 radix_tree_root 结构体进行了初始化。

第二种方法是手动定义radix_tree_root结构体,并且将它和mask传给 INIT_RADIX_TREE 宏:

struct radix_tree_root my_radix_tree;
INIT_RADIX_TREE(my_tree, gfp_mask_for_my_radix_tree);

INIT_RADIX_TREE 宏的定义如下:

#define INIT_RADIX_TREE(root, mask)  /
do {                                 /
        (root)->height = 0;          /
        (root)->gfp_mask = (mask);   /
        (root)->rnode = NULL;        /
} while (0)

RADIX_TREE_INIT宏所做的初始化工作一样,INIT_RADIX_TREE 宏使用默认值和给定的 mask 完成初始化工作。

接下来是用于向基数树插入和删除数据的两个函数:

  • radix_tree_insert;
  • radix_tree_delete;

第一个函数 radix_tree_insert 需要3个参数:

  • 基数树的根;
  • 索引键;
  • 插入的数据;

radix_tree_delete 函数需要和 radix_tree_insert 一样的一组参数,但是不需要传入要删除的数据。

基数树的搜索以两种方法实现:

  • radix_tree_lookup;
  • radix_tree_gang_lookup;
  • radix_tree_lookup_slot.

第一个函数radix_tree_lookup需要两个参数:

  • 基数树的根;
  • 索引键;

这个函数尝试在树中查找给定的键,并返回和该键相关联的记录。第二个函数 radix_tree_gang_lookup 有以下的函数签名:

unsigned int radix_tree_gang_lookup(struct radix_tree_root *root,
                                    void **results,
                                    unsigned long first_index,
                                    unsigned int max_items);

它返回的是记录的个数。 results 中的结果,按键排序,并从第一个索引开始。返回的记录个数将不会超过 max_items 的值。

最后一个函数radix_tree_lookup_slot将会返回包含数据的指针槽。

链接


via: https://github.com/0xAX/linux-insides/blob/master/DataStructures/radix-tree.md

作者:[0xAX] 译者:cposture 校对:Mr小眼儿

本文由 LCTT 原创翻译,Linux中国 荣誉推出

Linux 就在我们身边。它以 Android 的形式存在我们的手机中,它用在国际空间站中,它还是互联网的主要支柱,可是迄今为止很多人从未留意过它。对 Linux 的探索是一种很有成就感的尝试。很多人都在 Opensource.com 分享过他们与 Linux 的故事。现在,轮到我了。

我依然记得我在 2008 年第一次探索 Linux 的时刻。协助我探索 Linux 的人是我的父亲,Socrates Ballais。他是菲律宾塔克洛班的一名经济学专家,也是一个技术狂热者。他教会了我许多计算机技术方面的知识,但只提倡我将 Linux 作为 Windows 崩溃后的备用操作系统。

从前的日子

在我们在家中购置电脑之前,我曾是一个 Windows 用户。我使用电脑玩游戏,制作文档,做那些小孩子都会用电脑做的事。我不知道什么是 Linux,更不知道它的用处。在那个时候,电脑在我心中的象征就是一个 Windows 的商标。

当我们买到第一台电脑时,我爸爸在上面安装了 Linux (Ubuntu 8.04)。充满了好奇心的我,第一次引导进入了那个操作系统。我被它的用户界面震惊了。它非常漂亮,而且我发现它对用户很友好。在那之后的一段时间,我只会使用 Linux 它内置的几款游戏。我还是会在 Windows 中做我的家庭作业。

第一次安装

4 年后,我决定为家里的电脑重新安装 Windows。我同时毫不犹豫地安装了 Ubuntu。从那次开始,我(再次)爱上了 Linux。随着时间推移,我慢慢适应了 Ubuntu,还会无意地将它推荐给我的朋友。当我拿到我的第一台笔记本电脑时,我立刻在上面安装了它。

现在

如今,Linux 是我的默认操作系统。当我需要使用电脑做一些工作时,我会在 Linux 中完成。至于文档和幻灯片,我会通过 Wine 来使用微软的 Office 办公软件。我会用 Chrome 和 Firefox 来满足我的上网需要,会用 Geary 来收发邮件。你可以使用 Linux 来做很多很多事情。

我的大多数——并不是全部——编程工作都会在 Linux 中完成。像 Visual StudioXCode 这样的基本集成开发环境 (IDE) 的缺乏教会我这个程序员如何变得灵活、如何去学习更多知识。现在,我只需要一个文本编辑器和一个编译器/解释器就可以开始编程。只有当 IDE 是我完成手头上的任务的最佳最佳工具时,我才会使用它。总而言之,Linux 给了我开发软件所需要的一切工具。

现在,我是一个名叫 Creatomiv Studios 的初创公司的联合创始人和首席技术官。我使用 Linux 来编写我们的最新产品 Basyang 的后端服务器代码。我还是一个业余摄影家,使用 GIMPDarktable 来编辑、管理照片。至于团队沟通,我会使用 Telegram

Linux 之美

很多人认为 Linux 只是为那些喜欢解决复杂问题或者在命令行中工作的人而生的操作系统。还有些人会认为它就是一个缺乏公司支持维护的垃圾。不过,我认为 Linux 是一个完美的操作系统,也是一个为创造而生的绝佳工具。所以我热爱 Linux,同时希望看到它继续成长。


via: https://opensource.com/life/16/3/my-linux-story-sean-ballais

作者:Sean Francis N. Ballais 译者:StdioA 校对:wxy