NumPy's Blog

Nginx 红黑树设计 用于比较的关键字使用无符号整数 红黑树是一个通用的数据结构，它的节点可以是包含基本红黑树节点的任意结构体（与前面的循环链表类似，与具体业务数据解耦） Nginx 的核心模块（如定时器管理、文件缓存模块等）在需要快速检索、查找的场合下都使用了红黑树容器 Nginx 红黑树结构 root 指向树的根节点，如果红黑树为空，则指向哨兵节点 sentinel insert 表示红黑树添加元素的函数指针，它决定在添加新节点时的行为究竟是替换还是新增 struct ngx_rbtree_s { ngx_rbtree_node_t *root; ngx_rbtree_node_t *sentinel; ngx_rbtree_insert_pt insert; }; ngx_rbtree_insert_pt 的类型如下 typedef void (*ngx_rbtree_insert_pt) (ngx_rbtree_node_t *root, ngx_rbtree_node_t *node, ngx_rb ...

第一章小结 计算机硬件结构从总线型演进到南桥北桥，南桥负责处理低速设备如磁盘、键盘，北桥负责处理高速设备，如 cpu、内存等 计算机软件体系架构主要分四层，应用软件、操作系统 api（如glibc库）、系统调用、硬件 多道程序演进为多进程、多任务系统 设备驱动程序一般由硬件厂商提供，但是要遵循操作系统提供的接口和框架 早期的内存问题，如何将有限的物理内存分配给多个程序使用 地址空间不隔离：直接分配物理内存可能会导致内存数据被非法篡改，引入安全问题 内存使用效率低：内存不足时想要运行新程序，就需要将一些程序的数据从内存转移到磁盘，且只能全部转移 程序运行的地址不确定：程序每次需要装入运行时，都需要从内存中分配一块足够大的空闲区域，这个空闲区域的位置是不确定的 地址空间隔离的问题使用虚拟地址空间来解决，然后通过某种方式映射虚拟地址到物理地址，最初的方式是分段，这种方式虽然能够解决上述的问题 1 和问题 3，但是无法解决问题 2，后续引入了分页的方式，可以将一些不常用的页放到磁盘里存储，大大提高了内存利用效率 线程的访问权限 共享：全局变量、堆上的数据、函数里的静 ...

Nginx 字符串设计 用一个简单结构表示，字符串长度和指向字符串首地址的指针 用宏来创建、设置字符串结构体 创建都是用的字符串常量，其存放在数据段，生命期和整个程序一致 如果要在结构体成员中使用，则需要手动设置长度和数据指针 Nginx 字符串结构typedef struct { size_t len; u_char *data; } ngx_str_t; Nginx 字符串初始化 ngx_string 被大量使用，一般直接在程序中使用 ngx_string("xxx") 空字符串用 ngx_null_string 初始化 后两个操作分别设置一个 ngx_str_t 变量的值 #define ngx_string(str) { sizeof(str) - 1, (u_char *) str } #define ngx_null_string { 0, NULL } #define ngx_str_set(str, text) ...

Nginx 散列表设计 不支持动态增删改元素，初始化的时候就固定了整个哈希表的结构，只支持查找 以字符串作为关键字，键值可以是任意类型 有一种支持通配符的散列表变体，支持前缀和后缀通配符形式的关键字 解决散列冲突的方式本质上是分离链接法，但是由于不用支持动态增删，就不需要链表的动态插入特性，直接使用数组，可以增加访问的效率 字符串关键字在哈希表中是转换为小写字母存放的（重要） Nginx 散列表数据结构散列表结构 桶的数量为 size 每个桶可能含有多个槽数组，遍历槽类似于遍历链表，以一个 NULL 作为结尾typedef struct { ngx_hash_elt_t **buckets; ngx_uint_t size; } ngx_hash_t; 散列表槽结构 键值用 value 指向 关键字的长度用 len 表示 关键字用 name 保存，这里用到了柔性数组（flexible array），这里长度为 1 而不是 0 是出于可移植性的问题，有些编译器不支持零长度数组，好处就是少一次动态内存分配typedef struct ...

介绍nginx 一直采用多进程和 I/O 多路复用模型，在大部分场景下都有优秀的性能表现，但有时候耗时的阻塞操作会对性能产生一定的影响，例如从磁盘中读写大文件。因此在 1.7.11 版本 nginx 引入了线程池模块，用于处理耗时的阻塞操作，目前主要是文件读写、sendfile。具体的应用场景和性能分析可以参考以下文章： NGINX 中的线程池将性能提升 9 倍! Nginx 线程池实现 使用单链表实现队列结构，有一个等待队列和完成队列分别用于存放还没执行的任务和执行完毕的任务，之所以设计了一个完成队列是为了支持当任务完成后执行相应的回调函数 数据结构内存分配使用内存池 使用自旋锁优化并发操作性能，在临界区比较短的时候使用自旋锁可以得到比互斥锁更优的性能，在线程池中主要用在操作完成队列的时候 子线程 deatch 主线程不用 join，线程池销毁通过向队列中提交任务完成 Nginx 线程池数据结构线程任务结构 每一个线程任务都拥有一个 id 用于标识 由于使用链表实现任务独立，因此每个任务拥有指向下一个任务的指针 next 任务所要执行的函数用 handler 表示，其中函数的入 ...

概念自旋锁是一种基本的同步原语，用于实现多线程编程中的互斥访问控制。它通过循环自旋的方式等待获取锁，而不是将线程阻塞挂起。当自旋锁处于被占用状态时，线程会一直自旋等待直到锁可用。以下是自旋锁的一般特征和使用方式： 特征： 互斥性：自旋锁用于保护临界区，确保同时只有一个线程可以进入临界区执行操作，从而避免竞争条件和数据不一致性。 忙等待：当自旋锁已经被其他线程占用时，等待的线程会循环自旋（忙等待）直到获取到锁。 线程占用：一旦一个线程获取到自旋锁，其他线程必须等待该线程释放锁才能获取锁。 简单快速：相对于一些复杂的同步原语，自旋锁的实现通常较为简单且执行速度较快。 使用方式： 初始化：在使用自旋锁之前，需要对其进行初始化。 获取锁：当线程需要进入临界区时，调用获取锁的操作。如果锁已经被其他线程占用，则线程会不断自旋等待，直到获取到锁为止。 释放锁：当线程完成临界区的操作后，调用释放锁的操作，将锁标记为可用状态，允许其他线程获取锁。 需要注意的是，自旋锁适用于以下情况： 临界区的代码执行时间较短，自旋等待的时间较短，以避免线程阻塞和上下文切换的开销。 并发线程数相 ...

Nginx循环链表设计 采用双向链表数据结构实现 使用哨兵节点简化实现，避免多余的判断 链表结构不关联具体数据，业务结构体通过将链表结构作为成员从而支持链表操作（类似插件） 链表基础操作通过宏实现，同时支持自定义排序（使用稳定的插入排序） 双向链表基本操作 链表结构体只有两个指针，prev指向前一个节点，next指向下一个节点 typedef struct ngx_queue_s ngx_queue_t; struct ngx_queue_s { ngx_queue_t *prev; ngx_queue_t *next; }; 初始化：prev和 next都指向哨兵节点 #define ngx_queue_init(q) \ (q)->prev = q; \ (q)->next = q 判断链表是否为空： ...

Nginx链表设计 单链表数据结构，初始化后自带一个头结点 每一个链表节点存储一个动态数组，每次操作取一个数组元素内存 不支持删除节点，只能添加（尾插法） 使用内存池分配内存，只有当内存池释放时链表结构才能释放 创建链表 根据传入的数组大小 n和单个数组元素大小 size初始化链表结构 ngx_list_t * ngx_list_create(ngx_pool_t *pool, ngx_uint_t n, size_t size) { ngx_list_t *list; list = ngx_palloc(pool, sizeof(ngx_list_t)); if (list == NULL) { return NULL; } if (ngx_list_init(list, pool, n, size) != NGX_OK) { return NULL; } return list; } 链表初始化 初始化 part结构体成员 ...

Nginx 缓冲区设计 内存同样使用内存池进行分配 buffer 通过链表连接起来，不用了就回收到内存池的 chain buffer 结构体通过位域进行标识，节省内存空间 Nginx 缓冲区结构体组成struct ngx_buf_s { u_char *pos; u_char *last; off_t file_pos; off_t file_last; u_char *start; /* start of buffer */ u_char *end; /* end of buffer */ ngx_buf_tag_t tag; ngx_file_t *file; ngx_buf_t *shadow; /* the buf's content could be changed */ unsig ...

Nginx 数组设计 数组通过内存池分配内存 数组释放条件严格 支持动态扩容（2倍） 1. 数组创建 通过传入的内存池进行数组结构体的内存分配 进行数组成员初始化 ngx_array_t * ngx_array_create(ngx_pool_t *p, ngx_uint_t n, size_t size) { ngx_array_t *a; a = ngx_palloc(p, sizeof(ngx_array_t)); if (a == NULL) { return NULL; } if (ngx_array_init(a, p, n, size) != NGX_OK) { return NULL; } return a; } 2. 数组初始化 nelts 表示下一个待使用块的下标，初始为 0 size 为单个元素（块）的大小 nalloc 表示分配多少块内存，初始为 n elts 指向数组 ...