gin 发布的帖子
-
kernel list实现技巧
kernel list
实现技巧偶然间,翻到了一篇帖子下的评论说内核中的链表官方实现很巧妙,具有强大的通用性。于是我动手打开源码开始研究,内核链表实现通用性的方法与
kfifo
不仅异曲同工,甚至更加简洁优雅,实在是令我叹为观止。内核中维护的链表节点定义如下,非常简洁:
struct list_head { struct list_head *next, *prev; };
那么这个链表节点如何使用呢?巧妙之处又在哪里呢?
这里总结一下最朴素的链表实现方法,假设现在我们需要维护一个元素类型为
apple
的链表,我们一般会将链表元素定义为如下结构体:struct apple { unsigned int weight; char name[30]; ... struct apple *next, *prev; };
这样实现有什么问题呢?
-
通用性和代码可复用性。这样一来我们每定义一个类型的链表元素类型,都需要重新写一套新的API提供链表操作(插入,删除等)。
-
链表元素不能多样化。这样的实现方法就不可能满足链表元素多样化的需求。
Think outside the box! 这是我对内核链表官方实现的概括。这个implementation并不像
kfifo
一样exploit编译器的功能,相反,它是源自于算法层面的思考。我们一般的链表实现都是将元素插入链表里,但是内核链表官方实现的原理却是将共同的部分提取出来作为list_head
,而每个list_head
就相当于一个个衣架,而我们想要存储的元素就是一件件衣服,整个链表就是一个晾衣绳上用衣架挂着很多衣服。如何从
kernel list
中获得元素?内核中提供了
list_entry
这个API用来访问某个list_head
对应的链表元素。其定义如下:#define list_entry(ptr, type, member) container_of(ptr, type, member)
其中
ptr
是从内核链表中获得的一个list_head
指针;type
是链表元素的结构体类型;member
是list_head
在链表元素的结构体类型中定义的字段名称。对于内核中的通用性处理,我也会继续更新不同的内容。拜读大师们的作品,岂不乐乎?
-
-
kfifo算法原理
kfifo
的算法原理kfifo
本质上就是一个无锁队列,它的结构体如下:struct __kfifo { unsigned int in; unsigned int out; unsigned int mask; unsigned int esize; void *data; };
in
和out
分别指向入队和出队的位置。mask
等于队列长度减一。esize
是元素长度,也就是这个队列的颗粒度。队列默认的颗粒度是字节。讨论
mask
的作用,就不得不提及kfifo
的一个潜规则——队列长度一定为2的整数次幂。这样一来,对队列长度取模就可以直接利用mask & offset
的方法快速求得(取模运算耗时远高于位操作)。环形队列的一个关键问题就是——如何判断队列为空或者队列已经满了。一般的处理办法或许会在
in
和out
超过队列长度之后进行取模,让in
和out
两个指针始终保持在合法范围内。但是这就会产生一个难题——无法很简洁地区分队列为空和队列已满,因为这两个情况下都满足in==out
。此时就不得不在结构体里添加一个occupied_size
字段用来表示当前已入队的元素数量,这样显然并非最优解。而
kfifo
里是这样解决这个问题的:in
和out
不需要保证在合法范围内。此时就可以使用in-out
表示当前入队的元素数量。kfifo_put
和kfifo_get
的时候,需要对数组进行读写操作,此时数组的索引用in & mask
或out & mask
保证索引within range
。in
和out
的类型都是unsigned int
,它们溢出后不会有任何影响。因为对于unsigned int
这个类型而言,相减得到的结果是绝对值,所以比如说in
溢出后小于out
,但是in - out
得到的还是入队的元素数量。in == out
代表队列为空;in - out == mask + 1
表示队列已经满了。
-
errno in POSIX Threaded programs
What is
errno
?errno
is a positive integer.errno
is normally a global integer variable indicating the exact type of errors for most functions.errno
may also be a macro expanded into a function.
What is
errno
in a POSIX threaded program?errno
is defined as a macro expanded into a function__errno
which returns the pointer to the actualerrno
variable.- POSIX threaded function will return an error number same as the type of
errno
, which indicates the exact type of error.
The definition of
errno
#if defined(_REENTRANT) || _POSIX_C_SOURCE - 0 >= 199506L extern int *___errno(); #define errno (*(___errno())) #else extern int errno; /* ANSI C++ requires that errno be a macro */ #if __cplusplus >= 199711L #define errno errno #endif #endif /* defined(_REENTRANT) */
-
Linux重定向:从一句代码加深理解
1 重定向迷思:
touch test.txt echo hello > test.txt (cat; echo apple > /dev/stdin; cat) < test.txt
以上命令执行完毕后,标准输出流会输出
hello
,而没有apple
,为什么呢?
这个要从重定向的机制开始理解。Linux系统是以文件系统为核心理念的系统,即"一切都是文件"。而流也不例外,比如标准流有stdin
、stdout
和stderr
。这三者均有file descriptor
分别为0、1、2。而它们对应的文件均在/dev
目录下,分别为/dev/stdin
、/dev/stdout
和/dev/stderr
。
重定向的本质是将某个file descriptor
所操作的文件修改为命令中提供的文件。例如:ls -alF 2>/dev/null
就是将标准错误流
stderr
所写入的文件改为/dev/null
。
那么回到一开始的问题,为什么标准输出流只输出hello
呢?
在执行cat
的时候,标准输入流就已经指向了test.txt
,因此直接从标准输入流中读入内容,即为hello
。
但是,要注意到一个细节,和C语言一样,文件的读写是有位置的,即file position
,经过第一个指令后,标准输入流的file descriptor
已经读了6个字节了,即"hello"以及一个echo
默认自带的换行符。此时,echo
将字符串"apple"覆盖到/dev/stdin
中,但由于已经读了6个字符了,此时文件位置指向"apple"尾部的EOF
。
最后再执行cat
,读取/dev/stdin
的最后一个字符——EOF
,该字符在cat
下不会打印任何字符,只是终止cat
。2 重定向的语法:
一般来说,重定向有两种语法:为
file descriptor
打开一个新的文件,或者将某个file descriptor
修改为与另一个同类型修饰符操作同一个文件,简称复制修饰符(Duplicate Descriptor
)[n] > file
:为修饰符n
打开一个文件供其写入。若不给出n
则默认为标准输出流
[n] < file
: 为修饰符打开一个文件供其读取。若不给出n
则默认为标准输入流[n] >& m
: 将修饰符n
设置为与m
操作对象一致。默认为标准输出流。
[n] <& m
: 默认为标准输入流。
-
RE: POSIX规范下的正则表达式
@dorence 感谢分享,这里还有一份方便记忆的表格供大家参考 : )
POSIX Description ASCII Unicode Shorthand Java [:alnum:]
Alphanumeric characters [a-zA-Z0-9]
[\p{L}\p{Nl} \p{Nd}]
\p{Alnum}
[:alpha:]
Alphabetic characters [a-zA-Z]
\p{L}\p{Nl}
\p{Alpha}
[:ascii:]
ASCII characters [\x00-\x7F]
\p{InBasicLatin}
\p{ASCII}
[:blank:]
Space and tab [ \t]
[\p{Zs}\t]
\h
\p{Blank}
[:cntrl:]
Control characters [\x00-\x1F\x7F]
\p{Cc}
\p{Cntrl}
[:digit:]
Digits [0-9]
\p{Nd}
\d
\p{Digit}
[:graph:]
Visible characters (anything except spaces and control characters) [\x21-\x7E]
[^\p{Z}\p{C}]
\p{Graph}
[:lower:]
Lowercase letters [a-z]
\p{Ll}
\l
\p{Lower}
[:print:]
Visible characters and spaces (anything except control characters) [\x20-\x7E]
\P{C}
\p{Print}
[:punct:]
Punctuation (and symbols). [!"\#$%&'()*+,\-./:;<=>?@
[\\]^_‘{|}~] \p{P}
\p{Punct}
[:space:]
All whitespace characters, including line breaks [ \t\r\n\v\f]
[\p{Z}\t\r\n\v\f]
\s
\p{Space}
[:upper:]
Uppercase letters [A-Z]
\p{Lu}
\u
\p{Upper}
[:word:]
Word characters (letters, numbers and underscores) [A-Za-z0-9_]
[\p{L}\p{Nl} \p{Nd}\p{Pc}]
\w
\p{IsWord}
[:xdigit:]
Hexadecimal digits [A-Fa-f0-9]
[A-Fa-f0-9]
\p{XDigit}
-
POSIX规范下的正则表达式
1
POSIX
规范下的正则表达式在使用
ls
或者grep
等Linux命令时,会遇到需要使用正则表达式的场景,例如:ls [a-z]*
该命令将打印当前目录下以小写字母开头的文件
ls [^a-z]*
该命令将打印当前目录下除了以小写字母开头外的文件
但是,在实际操作的时候可能会遇到这样的情况,就是[a-z]*
并不能将文件名以小写字母开头的文件筛选出来,而是将以任意字母开头的文件全部打印出来,这又是为什么呢?
其实,我们只需要键入locale
命令,即可拿到当前系统环境下的本地设置:LANG=en_US.UTF-8 LANGUAGE= LC_CTYPE="en_US.UTF-8" LC_NUMERIC="en_US.UTF-8" LC_TIME="en_US.UTF-8" LC_COLLATE="en_US.UTF-8" LC_MONETARY="en_US.UTF-8" LC_MESSAGES="en_US.UTF-8" LC_PAPER="en_US.UTF-8" LC_NAME="en_US.UTF-8" LC_ADDRESS="en_US.UTF-8" LC_TELEPHONE="en_US.UTF-8" LC_MEASUREMENT="en_US.UTF-8" LC_IDENTIFICATION="en_US.UTF-8" LC_ALL=
看到第一行的
LANG
,查找相关资料发现,当LANG
为en_US.UTF-8
或者zh_CN.UTF-8
时,在系统的字符集里字母的排列并不是按照ASCII
码的顺序,即ABCDEFG...Zabcdefg...z
,而是aAbBcC...zZ
的顺序。如此便可以解释为什么一开始使用[a-z]
进行识别时不能筛选出小写字母。事实上,该正则表达式筛选出除Z外的所有字母。
如果想要正常筛选大写(或小写)字母,可以选择两种解决方式:- 设置
LC_ALL
:
LC_ALL=C ls [a-z]*
- 使用系统提供的字符类,比如
[[:lower:]]
,[[:upper:]]
,[[:digit:]]
等等,系统会根据当前的字符集保证字符类的正确性
在
C.UTF-8
和C
中的字符集是按照ASCII规范的,因此我们使用[a-z]
或[A-Z]
时是可以正常筛选大小写字母的。2 常见的正则表达式的标识符
*
:识别任意数量任意类型的字符(0个或任意多个)[]
: 方括号表达式识别括号内的任意一个字符。有三个需要注意的地方:[c-a]
是不合法的,不能识别任何字符。而[cba]
是合法的。形如[c-a]
的表达式一定要满足左边的字符要排在右边字符前面。- 方括号表达式还被用于表示系统预定义的字符类,如
[:lower:]
,[:upper:]
和[:digit:]
等。
^
: 表示“非”的意思,如[^[:lower:]]
可以识别除小写字母外所有的字符。
- 设置