书旅

书旅 查看完整档案

填写现居城市  |  填写毕业院校  |  填写所在公司/组织填写个人主网站
编辑

个人微信公众号:IT猿圈

个人动态

书旅 发布了文章 · 4月12日

吃透 Nginx 编译安装过程

编译出适合自己的Nginx

Nginx的安装方式

安装Nginx有两种方法,除了编译以外,还可以直接用操作系统上自带的一些工具,比如yum、apt-get

但是直接安装Nginx的二进制文件会有个问题,因为Nginx的二进制文件会把模块直接编译进来。Nginx的官方模块,并不是每一个都默认开启的,如果你想添加第三方的Nginx模块,你必须通过编译Nginx这种方式才能把第三方的模块添加到Nginx中

编译安装Nginx过程

下载Nginx

Nginx下载官网

进入官网之后,点击右下角的download
image.png

可以发现Nginx有两类版本,一个是Mainline version(最新版本)、一个是Stable version(稳定版本)。我们通常会选择下载稳定版本(这里最新的是1.18.0)
image.png

选择一个稳定版本,复制下载链接,通过wget的方式下载下来即可,下载下来之后是一个压缩包,通过下边命令解压即可

tar -xzf nginx-1.18.0.tar.gz
各目录介绍

进入解压之后的源码目录中,可以看到如下结构
image.png

  • auto目录
    image.png

其中cc目录是用于编译的,还有lib库,os目录是对所有的操作系统进行判断的。其它的文件都是为了在configure脚本执行的时候,去判定Nginx支持哪些模块,当前操作系统有什么样的特性可以供Nginx使用

  • CHANGES文件

CHANGES文件记录的是每个Nginx版本中提供了哪些特性和bugfix,部分内容截图
image.png

  • CHANGES.ru文件

因为Nginx作者是一个俄罗斯人,所以这是一个俄罗斯语言的CHANGES文件

  • conf目录
    image.png

它是一个示例目录,就是把Nginx安装完成以后,为了方便运维去配置,会把conf中的示例文件拷贝到安装目录

  • configure脚本

configure脚本是一个用来生成中间文件,执行编译前的必备动作

  • contrib目录
    image.png

它提供了两个脚本和vim的一个工具,比如在没有使用它提供的vim工具时打开Nginx的配置文件,会发现色彩没什么变化(可以看到Nginx配置文件的语法,没有在vim中高亮的显示)
image.png

然后现在将contrib目录中下的所有vim文件拷贝到本地安装的vim目录中

sudo cp -r contrib/vim/* ~/.vim/

然后再打开Nginx的配置文件
image.png

  • html目录
    image.png

该目录中提供了两个标准的html文件,一个是发现500错误的时候可以重定向到50x.html文件,另外一个是默认的Nginx欢迎界面

  • man目录

man目录是linux对Nginx的帮助文件(打开命令:man ./nginx.8)
image.png

  • src目录
    image.png

src目录是Nginx的源代码目录

Configure 编译

编译之前,可以看一下Configure支持哪些参数

./configure --help | more

image.png

它的参数里边主要分为几个大块:

  1. 第一类,确定Nginx执行中,它会去找哪些目录下的文件作为它的辅助文件。比如需要动态模块,此时 --modules-path=PATH 就会产生作用。如果没有任何变动的话,只需要指定 --prefix=PATH 这个参数就可以了,所有的其它的文件都会在prefix指定的目录下面建相应的文件夹
  2. 第二类,主要是确定使用和不使用哪些模块,它的前缀通常是 --with- 和 --without- 。比如说 --with-http_ssl_module 、 --with-http_v2_module,通常需要我们主动加--with模块的时候,意味着该模块默认是不会被编译进来的。而编译中需要使用 --without- ,意味着默认它会被编译进Nginx,如果你不加这个参数,他是会被编译进去,如果加了--without- ,它就不会被编译进去
  3. 第三类,指定了Nginx编译中需要的一些特殊的参数,比如用gcc编译的时候,需要加一些什么样的优化参数,或者说需要打印dubug级别的日志

image.png

下边就使用默认参数编译一下Nginx,下边指定了Nginx的安装目录

./configure --prefix=/home/geek/nginx

如果在执行的过程中没有报错,就意味着Nginx编译成功了。此时Nginx所有配置的特性,以及运行时的目录都会列在最下边
image.png

在上边编译完成之后,会生成一些中间文件

中间文件介绍

编译完成之后,生成的中间文件,会放在解压之后的nginx目录下的objs目录下
image.png

objs目录下文件结构
image.png
这里边最重要的是会生成一个文件叫ngx_modules.c,它决定了接下来执行编译的时候,有哪些模块会被编译进Nginx
image.png

每一行extern ngx_module_t 后边就是一个ngxin模块,所有会被编译进当前Nginx中的模块,都会被列在上边,他们最终会形成一个叫 *ngx_modules[]的指针数组

然后就可以执行make编译了。编译完成之后,会生成大量的中间文件,以及最终运行的Nginx二进制文件,可以在objs目录中看到
image.png

为什么需要知道Nginx的目标文件是放在这里的?

因为如果我们要做Nginx版本升级,此时不能执行make install,而是从这里把目标文件拷贝到安装目录中

C语言编译时生成的所有中间文件都会放在objs下的src目录下,如果我们使用了动态模块,编译时会生成动态文件,这个动态文件也会放在objs目录下。接下来就可以执行make install(首次安装时执行该命令)

执行完之后,就可以在--prefix执行的路径下看到如下结构
image.png
这里边最主要的Nginx二进制文件就在sbin目录下,决定Nginx功能的配置文件在conf目录下

可以看到在conf目录下,所有的文件就是在源代码中那个conf目录下所有文件copy过来了一份,内容也是一模一样的

以上便是Nginx的全部编译安装过程

Nginx配置文件通用语法介绍

  • Nginx配置文件中,已经指定了它包含了哪些模块,但每一个模块都提供独一无二的配置语法,这些所有的配置语法,会遵循同样的语法规则
  • 配置文件由指令与指令块构成
  • 每条指令以;分号结尾,指令与参数间以空格分隔
  • 指令块以{}大括号将多条指令组织在一起
  • include语句允许组合多个配置文件以提升可维护性
  • 使用#符合添加注释,提高可读性
  • 使用$符号使用变量
  • 部分指令的参数支持正则表达式

image.png

在http这个指令块下,通常有四个块:

  1. http
  2. server
  3. location
  4. upstream

http大括号下边就表示,里边所有的指令,都是由http模块去解析执行的,一个非http模块是没办法解析这里边的指令的。upstream则是表示上游服务,当Nginx需要与tomcat等其它服务交互的时候,可以定义一个upstreamserver则是对应一个域名,或者一组域名。location则是一个url表达式

查看原文

赞 0 收藏 0 评论 0

书旅 发布了文章 · 4月6日

初识Nginx(一)

由于Nginx对硬件和操作系统内核特性的深度挖掘,使得它在保持高并发的同时,实现了高吞吐量。优秀的模块设计,使得Nginx的生态圈,异常丰富。大量的第三方模块,使得Nginx可以轻松实现各种场景下的定制化需求

这些特性,使得Nginx成为互联网公司的标准配置

Nginx的三个主要应用场景

image.png

往往一个web请求从红色的箭头走下来以后,会先经过Nginx,再到应用服务,然后再去访问Redis或者MySQL这样的数据库,提供基本的数据功能

这里有一个问题,应用服务因为对开发效率要求特别的高,它的运行效率是很低的,它的QPS、TPS或者并发都是受限的,所以就需要把很多这样的应用服务组成一个集群,向用户提供高可用性,而一旦很多应用服务构成集群的时候,就需要Nginx具有反向代理功能,可以将动态请求传给应用服务

很多的应用服务组成的集群,它一定会带来两个需求:

  • 需要动态的扩容
  • 有些服务出问题的时候,需要做容灾

这样就使反向代理必须具备负载均衡功能。其次,在这样的一个链路中,Nginx是处在企业内部网络的边缘节点,随着网络链路的增长,用户体验到的时延会增加,所以如果我们能把一些用户看起来不变的,或者在一段时间内看起来不变的动态内容,缓存在Nginx部分,由Nginx直接向用户提供访问。那么这样用户访问时延就会减少很多

所以反向代理会衍生出另外一个功能叫缓存,它能加速访问。很多时候我们在访问css、js或者一些小的图标图片,这样的静态资源,是没有必要由应用服务来提供访问的,它只需要通过本地文件,系统上放置的静态资源,直接由Nginx提供访问就可以了,这就是Nginx提供静态资源服务功能

第三个应用场景,则是因为应用服务它本身的性能因为有很多的问题,但是数据库服务要比应用服务好的多,因为它的应用场景比较简单,它的并发性能和TPS都要远高于应用服务,所以就衍生出第三个应用场景。由Nginx直接去访问数据库(Redis或者类似这样的服务),利用Nginx强大的并发性实现如:web防火墙,这样复杂的业务功能来提供给用户。这要求API服务有非常强大的业务处理功能,所以像OpenResty,或者像Nginx集成的JavaScript,利用JavaScript、Lua这样的语言功能,和它们语言先天自带的一些工具库来提供完整的API服务

Nginx出现的历史背景

  • 互联网数据量的快速增长
  • 摩尔定律:性能提升
  • 低效的Apache

主要是全球化和物联网的快速发展,导致接入互联网的人与设备的数量都在快速上升,数据的快速爆炸,对硬件性能提出了很高的要求,提到硬件,大家都知道摩尔定律。之前我的服务跑在1GHz的CPU上,一年半以后,我更新到2GHz的CPU时,我可以预测到我的服务会有两倍的性能提升

但是到本世纪初,摩尔定律在单颗CPU的频率上已经失效了,CPU开始向多核方向发展。这个时候,当你的服务是跑在8核CPU上时,一年以后,你换到16核的CPU,通常你的服务不会有一倍的性能提升的

那么这些性能究竟损耗在哪里?

主要是操作系统和大量的软件没有做好服务于多核架构的准备,比如Apache,Apache是低效的,因为它的架构模型里,一个进程,同一时间,只会处理一个连接一个请求,只有在这个请求处理完以后,才会去处理下一个请求

这有什么潜台词呢?这实际上是在使用操作系统的进程间切换的特性,因为操作系统微观上只有有限的CPU,但是操作系统被设计为同时服务于数百甚至上千的进程,而Apache一个进程只能服务于一个连接,这样的模式,会导致,当Apache需要面对几十万、几百万连接的时候,它没有办法去开几百万的进程,而进程间切换的代价、成本又太高。当并发的连接数变多,这些进程间切换,引发的性能消耗也就越大。而Nginx是专门为了这样的应用场景而生的。Nginx可以处理数百万甚至数千万的并发连接

Nginx的优点

  • 高并发、高性能
  • 可扩展性好
  • 高可靠性
  • 热部署
  • BSD许可证
    image.png

它的Y轴是每秒处理的请求数(RPS),X轴是并发连接数。从图中可以看到,大部分的程序或web服务器,随着并发连接数的上升,它的RPS会急剧的下降,这就是上边说到的,它的架构设计是有问题的

Nginx的第一个优点就是高并发、高性能同时具备的,往往高并发只需要对每一个连接所使用的内存尽量的少就可以达到。而具备高并发的同时又具备高性能,往往需要非常好的设计。Nginx可以达到什么样的标准呢?比如说现在比较主流的服务器(32核、64G内存),可以轻松达到数千万的并发连接,如果是处理一些简单的静态资源请求,它可以达到100w的RPS

第二个核心优点是它的可扩展性非常的好。它的可扩展性主要体现在它的模块化设计,模块化设计的非常稳定,使得Nginx的第三方模块生态圈非常的丰富。丰富的生态圈,为Nginx丰富的功能提供了保证

第三个优点是它的高可靠性。所谓高可靠性是指Nginx可以在服务器上持续不间断的运行数年,而很多web服务器,往往运行几周或者几个月就需要做一次重启。对于Nginx这样一个高并发、高性能的反向代理服务器而言,它往往运行在企业内的边缘节点上,这个时候,如果企业想提供4个9,5个9,甚至更高的高可用性时,对Nginx持续运行,能够宕机的时间一年可能只能以秒来计。所以在这样一个角色中,Nginx的高可靠性,提供了非常好的保证

第四个优点是热部署。是指可以在不停止服务的情况下升级Nginx,这个功能对Nginx来讲非常重要,因为在Nginx上可能跑了数百万的并发连接。如果是普通的服务,我们可能是需要kill掉进程然后再重启的方式就可以处理好。但是对于Nginx而言,因为kill掉Nginx进程,会导致操作系统为所有的已经建立连接的客户端发送一个TCP中的reset复位包,而很多的客户端是没有办法很好的处理复位请求的。在大并发场景下,一些偶然事件,就会导致必然的恶性结果,所以热部署是非常有必要的

第五个优点是BSD许可证。它指的是Nginx不仅是开源的、免费的,而且大家可以在有定制的场景下去修改Nginx的源代码,在商业场景下是合法的

Nginx的四个主要组成部分

image.png

Nginx二进制可执行文件

这个是由Nginx本身的框架,它的官方模块和编译进去的各种第三方模块,一起构建的文件。这个文件就相当于汽车本身,它有完整的系统,所有的功能都由它提供

Nginx.conf配置文件

它相当于驾驶员,虽然二进制可执行文件已经提供了许多功能,但这些功能有没有开启,或者开启了以后,定义怎样的行为处理请求,都是由Nginx.conf配置文件决定的。所以它相当于驾驶员,控制汽车的行为

access.log访问日志

它相当于这辆汽车经过的所有地方形成了GPS轨迹,access.log会记录下每一条http请求信息与响应信息

error.log错误日志

它相当于黑匣子一样,当出现了一些不可预期的问题时,可以通过error.log去把问题定位出来

Nginx的版本发布情况

image.png

  • feature:发布了哪些功能
  • bugfix:修复了哪些bug
  • change:做了哪些小的重构
查看原文

赞 0 收藏 0 评论 0

书旅 发布了文章 · 1月22日

还热乎的面经

非常普通的二本菜鸟一枚(去年毕业),也一直有个大厂梦

回看2020,自己也确实比较结结实实的补了一波基础,虽然枯燥,但是过程中带来的成就感还是满满的。组内的几次分享,也让我对这些基础理解的较深刻

这也让我有了底气,在参加完好未来的PHP技术技术大会之后,决定尝试去面试大厂,检测一下自己的成果吧

从12.10~12.27,一共面了大概5家(包含好未来和百度),很幸运的都通过了所有技术面试,简直不敢相信(没见过世面的样子!-_-)

好了,下边才是本文主题,好未来和百度的面经(脑子容量有限,大概就记住下边这些。顺序没有先后,想起来一个写一个)

好未来面经

一面

  • 自我介绍
  • 介绍一下现在做的项目
  • 项目中遇到了哪些问题?是怎么解决的?
  • 项目中用到了哪些技术栈是你之前没有接触过的?是怎么学习的?
  • 给一个表结构,给一个SQL,问这个SQL查询过程是否有回表
  • 尽可能完整的描述MySQL执行一条SQL语句经历了哪些
  • 给一个打卡记录表,写一个SQL,获取到打卡次数最多的前10名
  • 给了一个有序数组,找出某个数字的下标
  • PHP7数组的底层实现(一面没答上来,确实没看过)
  • PHP是如何进行内存管理的
  • 进程、线程、协程的使用场景
  • Redis有哪些数据类型?缓存雪崩?缓存穿透?缓存击穿?
  • Nginx的多进程模型
  • 说说Laravel的服务容器
  • 502、504这两个状态码在什么情况下会出现?你是如何排查的?
  • 说一些你经常用到的查看系统情况的linux命令
  • 工作中用到了哪些设计模式

二面

  • 数组的移动:[1,2,3,4,5] 右移2位变成[4,5,1,2,3]
  • 单向链表环的检测
  • 给你一个无序数组,找到前K个最大的
  • Redis中,set、zset底层实现原理
  • Nginx如何实现平滑重启的?以什么方式?
  • Nginx和php的通信原理?
  • 详细说一下,哪些情况会出现502和504?
  • 项目中有哪些值得拿出来说的?
  • 信号监听这块怎么做的?kill -9 为什么能强杀进程
  • 进程间通信方式
  • PHP内存管理是怎么实现的?
  • PHP7数组的底层实现(一面之后看了一下,二面回答的时候,面试官说我描述的是PHP5的底层数组实现,PHP7有优化)
  • Redis中的zset,是如何实现扩容的?
  • 说一下依赖注入
  • 如果php-fpm没起来,Nginx会报哪个错误码
  • 你是如何提升接口QPS的
  • composer加载原理

hrbp面就没记录了,大致就是了解个人情况和如何学习之类的

好未来一直是我的目标公司,也是我毕业以来面的最大的厂(没办法,这学历,没人内推,很难有大厂的面试机会)。刚开始面的时候超忐忑,但是慢慢就进入状态了,每一轮面完真的成就感满满,不是说自己都会,而是面试官真的超好,你可能不是很清楚的地方,他一步步的去引导你,然后自己按照那个思路就找到答案了

面试感觉就是,面试官超专业,人也很好,反正感觉就特别好。面试通过,还是超级开心的。本来打算直接去好未来了,但是中间收到了百度的面试,所以就想试一下,很幸运也通过了,下边是百度的面经

百度面经

一面

  • 说说你现在做的项目(问的很细)
  • 说说你用go写的爬虫项目
  • 你的项目中用到了哪些数据结构
  • 你的爬虫项目如果做升级,你会怎么做?
  • 说说Redis的几种数据类型及使用场景
  • MySQL索引说一下,知道多少说多少
  • 括号匹配问题
  • 输出n对括号的所有组合(回溯,没答上来)
  • go里边的channel
  • 说一下你们对外的接口,如果用适配器模式进行修改,你会怎么做
  • Nginx和PHP通信的完整流程
  • Nginx的多进程模型
  • 如果Nginx的master进程被杀了之后,还能正常访问吗?

二面

  • 高并发有遇到过吗?(.....没有)
  • 有没有基于兴趣了解过分布式(......没有)
  • 说一下你理解的duck typing
  • go中的接口和php中的接口的区别
  • 你的项目中有哪些值得说的?
  • 知道什么是稳定排序吗?
  • 快排是稳定排序吗?为什么?还有哪些是不稳定排序?
  • 说一下同步、异步、阻塞、非阻塞、同步阻塞、异步阻塞、IO多复路
  • 进程间通信方式有哪些?
  • 乐观锁、悲观锁
  • MySQL用的是悲观锁还是乐观锁?
  • InnoDB和MyISAM的区别?Redis和Memcache的区别?你会在哪些场景下选择Memcache?
  • 你了解http和tcp吗?说一下你知道的内容
  • TCP、UDP的区别?什么是面向字节流的传输?
  • TCP是如何保证可靠传输的?
  • http的请求头内容和响应头内容有哪些
  • 说一下group by是如何实现的?

三面

  • 介绍一下现在和以前做的项目
  • 你项目中是如何保证幂等的
  • 双向链表,插入一个节点
  • MySQL的主从同步?如何保证顺序的?你有什么解决方案?(MySQL主从同步确实没仔细了解过,然后面试官就让说自己的思路)
  • PHP的垃圾回收机制
  • Redis中list的底层实现
  • 如何看待团队内部竞争的问题
  • 如果有个项目非常紧急,你如何做取舍
  • 有没有转go的想法
  • 三次握手?DOS攻击?
  • 如果有十条一样的单子并发请求到你的代码逻辑中,你会如何处理?

然后是hrbp面试,基本上是问一些在大学里都干了啥之类的

技术面试官真的都挺好的,也是一步步的引导你去思考问题,没有接触过没关系,说自己是如何思考的就行

然后很快也有了结果,通过了所有的面试。在面百度的期间,好未来那边已经跟我沟通完了所有的东西,就差发offer了。然后我是给好未来说我这边有百度的面试,想面完,好未来的hr真的超好,她说可以等百度这边给结果了再给她们回复

百度面完之后,它们招聘那边的人迟迟没联系我,后来我就主动问了一下,说今天就联系我,估计是它们把邮件忽略了。后边百度那边就给我发了入职材料的邮件,薪资流水、学历、学位这些

我确认百度这边通过之后,就把好未来的offer拒了。哎,可能只有学历非常普通的小伙伴才能理解吧,去百度是想镀一层金,平台大,有资源

但是在后边的沟通中,真的特别不舒服,跟我谈薪资的hr说话的方式,我真的超不喜欢。她给我的薪资,我觉得跟我预期的有点低,我说我考虑一下,然后稍后给回复。我记得她说了一句“年底了,我们hc少”,那个语气,大家自己悟。后来我接受了,为了镀金嘛

然后谈到入职时间的问题,对方说了一句“早点来对你有好处”,因为这个hr说话一直都是那种比较冷淡的,听到这句话我真的炸了。我是为了镀金,但也不能没底线,我就让她们终止流程了

我也知道那是她的职责,但是总觉得她姿态放的有点高,说话方式让人很有压迫感,我真不喜欢那种氛围

后来三面我的那个老大跟我了解了情况,说让再考虑一下。我最后还是选择了不去(我知道将来我不跟hr合作,技术团队的氛围并不会是那样,但是那种不舒服的感觉已经在心里了,很难再接受了)

然后我就联系了好未来的hr,问她们是否还有hc,我想再面一次。然后她问了我百度那边的情况,就跟她们那边主管商量,接着之前的流程走了

兜兜转转,也许它就是最好的结果。本身我也超喜欢好未来的技术氛围,也许这就是缘分,哈哈哈,加油!

好了,叨叨完了,希望大家也能拿到自己满意的offer!
image.png

查看原文

赞 0 收藏 0 评论 0

书旅 发布了文章 · 1月22日

2020年终总结:回顾、反思、期待

本文参与了SegmentFault 思否征文「2020 总结」,欢迎正在阅读的你也加入。

直到开始写年终总结的时候才发现,记日报的习惯,真的太好了,哈哈哈。因为这一年的所有事情都有迹可循,但是,记的太乱,整理起来是真的痛苦

我对2020的感觉就一个字:。真的莫名其妙感觉这一年过的飞快,2020对大多数人来说都是非常难的一年吧,只想说:乌云遮不住太阳,阴霾终究将散开,唯努力不会被辜负

下边开始我的叨叨叨

工作

因为年初疫情非常严重,所以年初的两个月左右都是在家办公。因为我在公司主要做的业务是TO B的,其实影响还是挺大的,基本上没什么新的商户接入进来,算是比较闲吧

但是年初因为出现了一个事故,也是折磨的挺够呛的,每天随时盯着报警,我记得那时候真是半夜起床上厕所都情不自禁的拿起手机看一下报警信息【手动捂脸】

也因为那次事故,公司开始要求,所有的需求不管大小,一律都必须写技术方案、过技术评审(初审、中审、大审)、codeReview,然后才能上线。之前都是大的需求才会去写技术方案、过技术评审之类的

刚开始其实挺不习惯的,但是当我在做监控和项目新版本的时候,发现写技术方案和严格的技术评审,还是帮自己学习到不少的,因为它能让自己思考的更仔细

今年感觉工作上最值得说的事情就是做我负责的这个项目的新版本吧,虽然做的很烂,但是收获是有的。非常感谢我老大敢让我去做吧,似乎是第一次做这么稍大的东西,很迷茫,基本上不知道怎么下手。我记得技术方案大概都过了三四次,很挫败,但是这期间的几次修改,确实让我收获挺多的,算是走出了某一步。上线之后接的第一个商户就是字节,幸运的是上线之后都没出现什么大的毛病【举止端庄、丝毫不慌】

恢复正常办公之后,公司组织架构做了调整,感觉影响还是挺大的。对我个人来说,感觉氛围好想没有了,再加上今年可能公司战略上的重点不在这个业务上,我们这边接入的商户少,需求也不多,算是比较闲。那时候心里挺慌的,因为一个月、两个月都感觉成长不大,现在去回想,感觉也怪自己不是那么主动的人吧,没有主动去争取很多事情来做

后边将近半年的工作基本上都很平淡,没有大的需求,都是小的改动和维护。自己也变的有点焦虑,后来是慢慢的把时间规划到技术学习和沉淀上边来了

这一年工作上的感触就是,没有量化自己的工作,虽然都有做日报,但是很乱,不方便做总结,所以今年打算学着量化自己的工作,把日报做的有序一些吧。这是新整的日报模板,以后就按这个来,哈哈哈

工作上算是平平淡淡的一年吧,年底跳到了另一家公司,希望能有更大的成长

学习

计算机基础

其实在2019年的年底就有计划在2020年恶补一波基础,所以从2020年的年初开始,我就从操作系统、计算机网络开始学吧(大学没重视,这就是代价吧)。大概到七月份,把操作系统、计算机网络的内容都大致学了一遍,并做了总结,整理到自己的公众号上。期间也看了《程序是怎样跑起来的》、《计算机是怎样跑起来的》、《网络是怎样连接的》,算是对操作系统和网络有了一个比较系统的认识吧

刚开始真觉得挺枯燥的,概念特别多。后来结合视频之类的,还是坚持下来了。中间在组内做了几次操作系统和网络的分享,效果不是很好,因为我讲的特别枯燥,大家都听不进去吧,而且一次准备的内容特别多

但是对我个人来说,收获是非常大的,深刻的感受到,你看懂了,和你能讲出来,差别非常大。因为我这个人在人多的时候分享,有点放不开,害怕出错。所以我都是每天晚上,照着ppt,给我女朋友去讲,相当于预先完整的讲一遍,看一下自己哪儿讲不清楚。分享的时候,我觉得自己说的还是比较流畅的,就是过于枯燥,想讲课一样,容易让人瞌睡

大杂烩

过完计算机操作系统、网络之后,大概七月份,那时候工作比较闲,老大让我们做每季度的学习成长计划,我记得我那边时候把每季度学的东西写的特别多,Laravel、MySQL进阶、设计模式等等,当时想的是都先过一遍,知道有这些东西

那时候我看了Laravel的进阶文档、《MySQL技术内幕:SQL编程》、《MySQL技术内幕:InnoDB存储引擎》、《MySQL5.7入门到精通》、《Docker技术入门与实战》。其实现在感觉,啥都没记住,没有专注于某一个,把精力弄的很分散

欲多则心散,心散则志衰。目标多了,精力就没法集中,精力没法集中,效率就降下来了。一次全力思考解决一个问题,才有可能陷入深思

GO

因为团队里边有用GO的想法,鼓励大家学GO,后边有项目想用GO进行改造。所以大概九月底开始学GO,看了两本书,每天早上边看边敲,差不多一个多月,对GO有一些认识,对基础的语法掌握的差不多了。然后写了一个简单的爬虫项目,之前对爬虫不了解,完全没接触过,这个项目之后,感觉学一个强类型的语言,太重要了啊,写GO的时候,个人感觉很多地方不容易憋过来

数据结构&算法

因为十月份左右的时候有了年后找新工作的想法,而数据结构和算法还是啃大学的底子。所以大概十一月份左右的时候开始系统的学习数据结构和做一些算法,也是用了差不多一个多月,跟着极客时间上边的《数据结构与算法之美》学习,感觉这个专栏写的特别的贴近平时的工作,把基础的数据结构大致学完一遍之后,感觉真的是有一个质的提升

在学的过程中,对每一个数据结构,都用GO敲一边,并把每一块自己觉得重要的地方,全部总结到自己的公众号上边

感觉2020年的学习成长这块,主要精力还是在基础上边的。要说今年学习了这些基础之后,有啥感觉没有,那必须是有的,看MySQL、Redis、Nginx的底层的时候,真的是轻松很多啊!以前看到一个概念就查一个概念,没多久就坚持不住了,现在真的是轻松多了

还是一直坚信,有了扎实的基础才能走的更远

生活

理财入门

2020年下半年开始学习理财,也是慢慢的才发现理财的重要性。我的习惯,在开始了解任何一块知识之前,先找找相关的书看看《小狗钱钱1》、《小狗钱钱2》、《穷爸爸富爸爸》、《指数基金定投实战宝典》、《手把手教你买基金》,大概看了这么几本,前边三本真是刷新了很多我对于金钱的认知,强烈推荐

刚开始因为不是很了解,所以就买了一些简单的基金,因为担心风险,所以货币基金买的比较多,然后慢慢的才开始买指数基金,经过半年,也小有收益吧,很开心

理财其实并不只是说让自己的资金保值或增值,它不等于把自己该存下来的钱都拿去买基金之类的。买基金的钱应该 = 收入 - 固定开支 - 商业保险 - 储蓄,个人是这么感觉的

当然,我更赞成,开源节流比研究各种理财产品、基金更重要。所以在2021年,打算清楚的记录自己的所有收入与开销,然后去优化。其次才是买基金之类的

昨晚熬夜整理了一个记账本(Excel真的太神奇了)

记账本-收入

记账本-支出

理财报表

开源节流一定不等于降低生活质量,主要是要先知道自己的每一分钱流向了哪里,然后每月进行分析,是否有花的不合理的地方,比如因为头脑一热买了根本不需要的东西。然后对开销进行优化

厦门遗憾

厦门真的是我从高中开始就特别想去的地方,脑海中的它就是依山傍海,非常美的城市。再加上本人是一个喜欢海,但又从来没见过海的孩子,所以对厦门的海,有种莫名的向往

去年六月初,做好了厦门旅行的攻略、定了机票、住宿,假都提前请了。然后家里出了点事情,不得不回家,厦门之旅就成了一个遗憾。虽然我没去成,但是女票这种对厦门没啥向往的人却去了。那句话怎么说来着,文化水平有限,那句话也不知道咋说【手动狗头保命】

海南之旅

因为女票九月份去了海南,之后一直在那边准备考研。十一月底的时候,终于实现了今年的首次出行,目标:海南。因为海南算是一个岛,我就幻想着,第一次看见海一定会是在飞机上,肯定很壮观。巧了不是,没靠窗的座了

到海南之后的第一感觉就是,原来天可以这么广阔,海南的路也特别宽,路上人很少。在公交上的时候经过海边,差点都想下去了【没见过世面的样子,哈哈哈】

见到女票之后,第一件事情当然就是去海边了。穿着酒店的拖鞋就出门了,分分钟走到海边

感觉海南是个特别安静的城市,适合生活,哈哈哈

今年必然找机会去厦门,期待!

期待

2021,新的一年,也马上进入新的环境,希望可以快速融入、快速适应吧,心里有点慌,但更多的还是期待

这一年就三个目标:自律、学习理财、技术沉淀

天色才刚刚破晓,加油!

查看原文

赞 0 收藏 0 评论 0

书旅 赞了文章 · 2020-12-14

【PHP7源码分析】PHP内存管理

作者: 顺风车运营研发团队 李乐

第一章 从操作系统内存管理说起

程序是代码和数据的集合,进程是运行着的程序;操作系统需要为进程分配内存;进程运行完毕需要释放内存;内存管理就是内存的分配和释放;

1. 分段管理

分段最早出现在8086系统中,当时只有16位地址总线,其能访问的最大地址是64k;当时的内存大小为1M;如何利用16位地址访问1M的内存空间呢?

于是提出了分段式内存管理;
将内存地址分为段地址与段偏移,段地址会存储在寄存器中,段偏移即程序实际使用的地址;当CPU需要访问内存时,会将段地址左移4位,再加上段偏移,即可得到物理内存地址;
即内存地址=段地址*16+段偏移地址。

后来的IA-32在内存中使用一张段表来记录各个段映射的物理内存地址,CPU只需要为这个段表提供一个记录其首地址的寄存器就可以了;如下图所示:

图片描述

进程包含多个段:代码段,数据段,链接库等;系统需要为每个段分配内存;
一种很自然地想法是,根据每个段实际需要的大小进行分配,并记录已经占用的空间和剩余空间:
当一个段请求内存时,如果有内存中有很多大小不一的空闲位置,那么选择哪个最合理?

a)首先适配:空闲链表中选择第一个位置(优点:查表速度快) 
b)最差适配:选择一个最大的空闲区域 
c)最佳适配:选择一个空闲位置大小和申请内存大小最接近的位置,比如申请一个40k内存,而恰巧内存中有一个50k的空闲位置;

内存分段管理具有以下优点:

a)内存共享: 对内存分段,可以很容易把其中的代码段或数据段共享给其他程序;
b)安全性: 将内存分为不同的段之后,因为不同段的内容类型不同,所以他们能进行的操作也不同,比如代码段的内容被加载后就不应该允许写的操作,因为这样会改变程序的行为
c)动态链接: 动态链接是指在作业运行之前,并不把几个目标程序段链接起来。要运行时,先将主程序所对应的目标程序装入内存并启动运行,当运行过程中又需要调用某段时,才将该段(目标程序)调入内存并进行链接。

尽管分段管理的方式解决了内存的分配与释放,但是会带来大量的内存碎片;即尽管我们内存中仍然存在很大空间,但全部都是一些零散的空间,当申请大块内存时会出现申请失败;为了不使这些零散的空间浪费,操作系统会做内存紧缩,即将内存中的段移动到另一位置。但明显移动进程是一个低效的操作。

2.分页管理

先说说虚拟内存的概念。CPU访问物理内存的速度要比磁盘快的多,物理内存可以认为是磁盘的缓存,但物理内存是有限的,于是人们想到利用磁盘空间虚拟出的一块逻辑内存
(这部分磁盘空间Windows下称之为虚拟内存,Linux下被称为交换空间(Swap Space));

虚拟内存和真实的物理内存存在着映射关系;

为了解决分段管理带来的碎片问题,操作系统将虚拟内存分割为虚拟页,相应的物理内存被分割为物理页;而虚拟页和物理页的大小默认都是4K字节;

操作系统以页为单位分配内存:假设需要3k字节的内存,操作系统会直接分配一个4K页给进程
,这就产生了内部碎片(浪费率优于分段管理)

前面说过,物理内存可以认为是磁盘的缓存;虚拟页首先需要分配给进程并创建与物理页的映射关系,然后才能将磁盘数据载入内存供CPU使用;由此可见,虚拟内存系统必须能够记录一个虚拟页是否已经分配给进程;是否已经将磁盘数据载入内存,对应哪个物理页;假如没有载入内存,这个虚拟页存放在磁盘的哪个位置;
于是虚拟页可以分为三种类型:已分配,未缓存,已缓存;

当访问没有缓存的虚拟页时,系统会在物理内存中选择一个牺牲页,并将虚拟页从磁盘赋值到物理内存,替换这个牺牲页;而如果这个牺牲页已经被修改,则还需要写回磁盘;这个过程就是所谓的缺页中断;

虚拟页的集合就称为页表(pageTable),页表就是一个页表条目(page table entry)的数组;每个页表条目都包含有效位标志,记录当前虚拟页是否分配,当前虚拟页的访问控制权限;同时包含物理页号或磁盘地址;

图片描述

进程所看到的地址都是虚拟地址;在访问虚拟地址时,操作系统需要将虚拟地址转化为实际的物理地址;而虚拟地址到物理地址的映射是存储在页表的;

将虚拟地址分为两部分:虚拟页号,记录虚拟页在页表中的偏移量(相当于数组索引);页内偏移量;而页表的首地址是存储在寄存器中;

图片描述

对于32位系统,内存为4G,页大小为4K,假设每个页表项4字节;则页表包含1M个页表项,占用4M的存储空间,页表本身就需要分配1K个物理页;
页表条目太大时,页表本身需要占用更多的物理内存,而且其内存还必须是连续的;

目前有三种优化技术:

1)多级页表
一级页表中的每个PTE负责映射虚拟地址空间中一个4M的片(chunk),每一个片由1024个连续的页面组成;二级页表的每个PTE都映射一个4K的虚拟内存页面;

优点:节约内存(假如一级页表中的PTE为null,则其指向的二级页表就不存在了,而大多数进程4G的虚拟地址空间大部分都是未分配的;只有一级页表才总是需要在主存中,系统可以在需要的时候创建、调入、调出二级页表)
缺点:虚拟地址到物理地址的翻译更复杂了

图片描述

2)TLB
多级页表可以节约内存,但是对于一次地址翻译,增加了内存访问次数,k级页表,需要访问k次内存才能完成地址的翻译;

由此出现了TLB:他是一个更小,访问速度更快的虚拟地址的缓存;当需要翻译虚拟地址时,先在TLB查找,命中的话就可以直接完成地址的翻译;没命中再页表中查找;

图片描述

3)hugePage

因为内存大小是固定的,为了减少映射表的条目,可采取的办法只有增加页的尺寸。hugePage便因此而来,使用大页面2m,4m,16m等等。如此一来映射条目则明显减少。

3.linux虚拟内存

linux为每个进程维护一个单独的虚拟地址空间,进程都以为自己独占了整个内存空间,如图所示:

图片描述
linux将内存组织为一些区域(段)的集合,如代码段,数据段,堆,共享库段,以及用户栈都是不同的区域。每个存在的虚拟页面都保存在某个区域中,不属于任何一个区域的虚拟页是不存在的,不能被进程使用;

![clipboard.png](/img/bV9623)

内核为系统中的每个进程维护一个单独的任务结构task_struct,任务中的一个字段指向mm_struct,他描述了虚拟内存的当前状态。其中包含两个字段:pgd指向第一级页表的基址(当内核运行这个进程时,就将pgd的内容存储在cr3控制寄存器中);mmap指向一个vm_area_struct区域结构的链表;区域结构主要包括以下字段:
vm_start:区域的起始地址;
vm_end:区域的结束地址;
vm_port:指向这个区域所包含页的读写许可权限;
vm_flags:描述这个区域是与其他进程共享的,还是私有的等信息;

当我们访问虚拟地址时,内核会遍历vm_area_struct链表,根据vm_start和vm_end能够判断地址合法性;根据vm_por能够判断地址访问的合法性;
遍历链表时间性能较差,内核会将vm_area_struct区域组织成一棵树;

说到这里就不得不提一下系统调用mmap,其函数声明为

void* mmap ( void * addr , size_t len , int prot , int flags , int fd , off_t offset )

函数mmap要求内核创建一个新的虚拟内存区域(注意是新的区域,和堆是平级关系,即mmap函数并不是在堆上分配内存的,);最好是从地址addr开始(一般传null),并将文件描述fd符指定的对象的一个连续的chunk(大小为len,从文件偏移offset开始)映射到这个新的区域;当fd传-1时,可用于申请分配内存;

参数port描述这个区域的访问控制权限,可以取以下值:

PROT_EXEC //页内容可以被执行
PROT_READ //页内容可以被读取
PROT_WRITE //页可以被写入
PROT_NONE //页不可访问

参数flags由描述被映射对象类型的位组成,如MAP_SHARED 表示与其它所有映射这个对象的进程共享映射空间;MAP_PRIVATE 表示建立一个写入时拷贝的私有映射,内存区域的写入不会影响到原文件。

php在分配2M以上大内存时,就是直接使用mmap申请的;

第二章 说说内存分配器

malloc是c库函数,用于在堆上分配内存;操作系统给进程分配的堆空间是若干个页,我们再调用malloc向进程请求分配若干字节大小的内存;
malloc就是一种内存分配器,负责堆内存的分配与回收;

同样我们可以使用mmap和munmap来创建和删除虚拟内存区域,以达到内存的申请与释放;

观察第一章第三小节中的虚拟地址空间描述图,每个进程都有一个称为运行时堆的虚拟内存区域,操作系统内核维护着一个变量brk,指向了堆的顶部;并提供系统调用brk(void* addr)和sbrk(incr)来修改变量brk的值,从而实现堆内存的扩张与收缩;

brk函数将brk指针直接设置为某个地址,而sbrk函数将brk从当前位置移动incr所指定的增量;(如果将incr设置为0,则可以获得当前brk指向的地址)

因此我们也可以使用brk()或sbrk()来动态分配/释放内存块;

需要注意的一点是:系统为每一个进程所分配的资源不是无限的,包括可映射的内存空间,即堆内存并不是无限大的;所以当调用malloc将堆内存都分配完时,malloc会使用mmap函数额外再申请一个虚拟内存区域(由此发现,使用malloc申请的内存也并不一定是在堆上)

1.内存分配器设计思路

内存分配器用于处理堆上的内存分配或释放请求;

要实现分配器必须考虑以下几个问题:

1.空闲块组织:如何记录空闲块;如何标记内存块是否空闲;
2.分配:如何选择一个合适的空闲块来处理分配请求;
3.分割:空闲块一般情况会大于实际的分配请求,我们如何处理这个空闲块中的剩余部分;
4.回收:如何处理一个刚刚被释放的块;

思考1:空闲块组织
内存分配与释放请求时完全随机的,最终会造成堆内存被分割为若干个内存小块,其中有些处于已分配状态,有些处于空闲状态;我们需要额外的空间来标记内存状态以及内存块大小;
下图为malloc设计思路:
clipboard.png

注:图中显示额外使用4字节记录当前内存块属性,其中3比特记录是否空闲,29比特记录内存块大小;实际malloc头部格式可能会根据版本等调整;不论我们使用malloc分配多少字节的内存,实际malloc分配的内存都会多几个字节;
注:空闲内存块可能会被组织为一个链表结构,由此可以遍历所有空闲内存块,直到查找到一个满足条件的为止;

思考2:如何选择合适的空闲块
在处理内存分配请求时,需要查找空闲内存链表,找到一个满足申请条件的空闲内存块,选择什么查找算法;而且很有可能存在多个符合条件的空闲内存块,此时如何选择?
目前有很多比较成熟的算法,如首次适配,最佳适配,最差适配等;

思考3:如何分配
在查找到满足条件的空闲内存块时,此内存一般情况会比实际请求分配的内存空间要大;全部分配给用户,浪费空间;因此一般会将此空闲内存块切割为两个小块内存,一块分配给用户,一块标记为新的空闲内存

思考4:如何回收:
当用户调用free()函数释放内存时,需要将此块内存重新标记为空闲内存,并且插入空闲链表;然而需要注意的是,此块内存可能能够与其他空闲内存拼接为更大的空闲内存;此时还需要算法来处理空闲内存的合并;

思考5:内存分配效率问题:
用户请求分配内存时,需要遍历空闲内存链表,直到查找到一个满足申请条件的空闲内存;由此可见,算法复杂度与链表长度成正比;
我们可以将空闲内存按照空间大小组织为多个空闲链表,内存大小相近的形成一个链表;此时只需要根据申请内存大小查找相应空闲链表即可;
更进一步的,空闲内存只会被切割为固定大小,如2^n字节,每种字节大小的空闲内存形成一个链表;(用户实际分配的内存是2^n字节,大于用户实际请求)

总结:任何内存分配器都需要额外的空间(数据结构)记录每个内存块大小及其分配状态;

第三章 内存池

C/C++下内存管理是让几乎每一个程序员头疼的问题,分配足够的内存、追踪内存的分配、在不需要的时候释放内存——这个任务相当复杂。而直接使用系统调用malloc/free、new/delete进行内存分配和释放,有以下弊端:

调用malloc/new,系统需要根据“最先匹配”、“最优匹配”或其他算法在内存空闲块表中查找一块空闲内存,调用free/delete,系统可能需要合并空闲内存块,这些都会产生额外的开销;
频繁使用时会产生大量内存碎片,从而降低程序运行效率;
容易造成内存泄漏;

内存池(memory pool)是代替直接调用malloc/free、new/delete进行内存管理的常用方法,当我们申请内存空间时,首先到我们的内存池中查找合适的内存块,而不是直接向操作系统申请,优势在于:

比malloc/free进行内存申请/释放的方式快
不会产生或很少产生堆碎片
可避免内存泄漏

内存池一般会组织成如下结构:
结构中主要包含block、list 和pool这三个结构体,block结构包含指向实际内存空间的指针,前向和后向指针让block能够组成双向链表;list结构中free指针指向空闲 内存块组成的链表,used指针指向程序使用中的内存块组成的链表,size值为内存块的大小,list之间组成单向链表;pool结构记录list链表的头和尾。

当用户申请内存时,只需要根据所申请内存的大小,遍历list链表,查看是否存在相匹配的size;

clipboard.png

第四章 切入主题——PHP内存管理

PHP并没有直接使用现有的malloc/free来管理内存的分配和释放,而是重新实现了一套内存管理方案;

PHP采取“预分配方案”,提前向操作系统申请一个chunk(2M,利用到hugepage特性),并且将这2M内存切割为不同规格(大小)的若干内存块,当程序申请内存时,直接查找现有的空闲内存块即可;

PHP将内存分配请求分为3种情况:

huge内存:针对大于2M-4K的分配请求,直接调用mmap分配;

large内存:针对小于2M-4K,大于3K的分配请求,在chunk上查找满足条件的若干个连续page;

small内存:针对小于3K的分配请求;PHP拿出若干个页切割为8字节大小的内存块,拿出若干个页切割为16字节大小的内存块,24字节,32字节等等,将其组织成若干个空闲链表;每当有分配请求时,只在对应的空闲链表获取一个内存块即可;

1.PHP内存管理器数据模型

1.1结构体

PHP需要记录申请的所有chunk,需要记录chunk中page的使用情况,要记录每种规格内存的空闲链表,要记录使用mmap分配的huge内存,等等…………

于是有了以下两个结构体:
_zend_mm_heap记录着内存管理器所需的所有数据:

//省略了结构体中很多字段
struct _zend_mm_heap {
    //统计
    size_t             size;                    /* current memory usage */
    size_t             peak;                    /* peak memory usage */
    //由于“预分配”方案,实际使用内存和向操作系统申请的内存大小是不一样的;
    size_t             real_size;               /* current size of allocated pages */
    size_t             real_peak;               /* peak size of allocated pages */
 
    //small内存分为30种;free_slot数组长度为30;数组索引上挂着内存空闲链表
    zend_mm_free_slot *free_slot[ZEND_MM_BINS]; /* free lists for small sizes */
 
    //内存限制
    size_t             limit;                   /* memory limit */
    int                overflow;                /* memory overflow flag */
 
    //记录已分配的huge内存
    zend_mm_huge_list *huge_list;               /* list of huge allocated blocks */
 
    //PHP会分配若干chunk,记录当前主chunk首地址
    zend_mm_chunk     *main_chunk;
     
    //统计chunk数目
    int                chunks_count;            /* number of alocated chunks */
    int                peak_chunks_count;       /* peak number of allocated chunks for current request */ 
}

_zend_mm_chunk记录着当前chunk的所有数据

struct _zend_mm_chunk {
    //指向heap
    zend_mm_heap      *heap;
    //chunk组织为双向链表
    zend_mm_chunk     *next;
    zend_mm_chunk     *prev;
    //当前chunk空闲page数目
    uint32_t           free_pages;              /* number of free pages */
    //当前chunk最后一个空闲的page位置
    uint32_t           free_tail;               /* number of free pages at the end of chunk */
    //每当申请一个新的chunk时,这个chunk的num会递增
    uint32_t           num;
    //预留
    char               reserve[64 - (sizeof(void*) * 3 + sizeof(uint32_t) * 3)];
    //指向heap,只有main_chunk使用
    zend_mm_heap       heap_slot;               /* used only in main chunk */
    //记录512个page的分配情况;0代表空闲,1代表已分配
    zend_mm_page_map   free_map;                /* 512 bits or 64 bytes */
    //记录每个page的详细信息,
    zend_mm_page_info  map[ZEND_MM_PAGES];      /* 2 KB = 512 * 4 */
};

1.2small内存

前面讲过small内存分为30种规格,每种规格的空闲内存都挂在_zend_mm_heap结构体的free_slot数组上;
30种规格内存如下:

//宏定义:第一列表示序号(称之为bin_num),第二列表示每个small内存的大小(字节数);
//第四列表示每次获取多少个page;第三列表示将page分割为多少个大小为第一列的small内存;
#define ZEND_MM_BINS_INFO(_, x, y) \
    _( 0,    8,  512, 1, x, y) \
    _( 1,   16,  256, 1, x, y) \
    _( 2,   24,  170, 1, x, y) \
    _( 3,   32,  128, 1, x, y) \
    _( 4,   40,  102, 1, x, y) \
    _( 5,   48,   85, 1, x, y) \
    _( 6,   56,   73, 1, x, y) \
    _( 7,   64,   64, 1, x, y) \
    _( 8,   80,   51, 1, x, y) \
    _( 9,   96,   42, 1, x, y) \
    _(10,  112,   36, 1, x, y) \
    _(11,  128,   32, 1, x, y) \
    _(12,  160,   25, 1, x, y) \
    _(13,  192,   21, 1, x, y) \
    _(14,  224,   18, 1, x, y) \
    _(15,  256,   16, 1, x, y) \
    _(16,  320,   64, 5, x, y) \
    _(17,  384,   32, 3, x, y) \
    _(18,  448,    9, 1, x, y) \
    _(19,  512,    8, 1, x, y) \
    _(20,  640,   32, 5, x, y) \
    _(21,  768,   16, 3, x, y) \
    _(22,  896,    9, 2, x, y) \
    _(23, 1024,    8, 2, x, y) \
    _(24, 1280,   16, 5, x, y) \
    _(25, 1536,    8, 3, x, y) \
    _(26, 1792,   16, 7, x, y) \
    _(27, 2048,    8, 4, x, y) \
    _(28, 2560,    8, 5, x, y) \
    _(29, 3072,    4, 3, x, y)
 
#endif /* ZEND_ALLOC_SIZES_H */

只有这个宏定义有些功能不好用程序实现,比如bin_num=15时,获得此种small内存的字节数?分配此种small内存时需要多少page呢?
于是有了以下3个数组的定义:

//bin_pages是一维数组,数组大小为30,数组索引为bin_num,
//数组元素为ZEND_MM_BINS_INFO宏中的第四列
#define _BIN_DATA_PAGES(num, size, elements, pages, x, y) pages,
static const uint32_t bin_pages[] = {
  ZEND_MM_BINS_INFO(_BIN_DATA_PAGES, x, y)
};
//bin_elements是一维数组,数组大小为30,数组索引为bin_num,
//数组元素为ZEND_MM_BINS_INFO宏中的第三列
#define _BIN_DATA_ELEMENTS(num, size, elements, pages, x, y) elements,
static const uint32_t bin_elements[] = {
  ZEND_MM_BINS_INFO(_BIN_DATA_ELEMENTS, x, y)
};
//bin_data_size是一维数组,数组大小为30,数组索引为bin_num,
//数组元素为ZEND_MM_BINS_INFO宏中的第二列
#define _BIN_DATA_SIZE(num, size, elements, pages, x, y) size,
static const uint32_t bin_data_size[] = {
  ZEND_MM_BINS_INFO(_BIN_DATA_SIZE, x, y)
};

2.PHP small内存分配方案

2.1设计思路

上一节提到PHP将small内存分为30种不同大小的规格;
每种大小规格的空闲内存会组织为链表,挂在数组_zend_mm_heap结构体的free_slot[bin_num]索引上;

clipboard.png

回顾下free_slot字段的定义:

zend_mm_free_slot *free_slot[ZEND_MM_BINS];
 
struct zend_mm_free_slot {
    zend_mm_free_slot *next_free_slot;
};

可以看出空闲内存链表的每个节点都是一个zend_mm_free_slot结构体,其只有一个next指针字段;

思考:对于8字节大小的内存块,其next指针就需要占8字节的空间,那用户的数据存储在哪里呢?
答案:free_slot是small内存的空闲链表,空闲指的是未分配内存,此时是不需要存储其他数据的;当分配给用户时,此节点会从空闲链表删除,也就不需要维护next指针了;用户可以在8字节里存储任何数据;

思考:假设调用 void*ptr=emalloc(8)分配了一块内存;调用efree(ptr)释放内存时,PHP如何知道这块内存的字节数呢?如何知道这块内存应该插入哪个空闲链表呢?
思考1:第二章指出,任何内存分配器都需要额外的数据结构来标志其管理的每一块内存:空闲/已分配,内存大小等;PHP也不例外;可是我们发现使用emalloc(8)分配内存时,其分配的就只是8字节的内存,并没有额外的空间来存储这块内存的任何属性;
思考2:观察small内存宏定义ZEND_MM_BINS_INFO;我们发现对于每一个page,其只可能被分配为同一种规格;不可能存在一部分分割为8字节大小,一部分分割为16字节大小;也就是说每一个page的所有small内存块属性是相同的;那么只需要记录每一个page的属性即可;
思考3:large内存是同样的思路;申请large内存时,可能需要占若干个page的空间;但是同一个page只会属于一个large内存,不可能将一个page的一部分分给某个large内存;
答案:不管page用于small内存还是large内存分配,只需要记录每一个page的属性即可,PHP将其记录在zend_mm_chunk结构体的zend_mm_page_info map[ZEND_MM_PAGES]字段;长度为512的int数组;对任一块内存,只要能计算出属于哪一个页,就能得到其属性(内存大小);

2.2入口API

//内存分配对外统一入口API为_emalloc;函数内部直接调用zend_mm_alloc_heap,
//其第一个参数就是zend_mm_heap结构体(全局只有一个),第二个参数就是请求分配内存大小
void*  _emalloc(size_t size)
{
    return zend_mm_alloc_heap(AG(mm_heap), size);
}
//可以看出其根据请求内存大小size判断分配small内存还是large内存,还是huge内存
static void *zend_mm_alloc_heap(zend_mm_heap *heap, size_t size)
{
    void *ptr;
 
    if (size <= ZEND_MM_MAX_SMALL_SIZE) {
        
        ptr = zend_mm_alloc_small(heap, size, ZEND_MM_SMALL_SIZE_TO_BIN(size));   
        //注意ZEND_MM_SMALL_SIZE_TO_BIN这个宏定义
        
        return ptr;
    } else if (size <= ZEND_MM_MAX_LARGE_SIZE) {
        ptr = zend_mm_alloc_large(heap, size);
        return ptr;
    } else {
        return zend_mm_alloc_huge(heap, size);
    }
}
 
 //使用到的宏定义如下
#define ZEND_MM_CHUNK_SIZE (2 * 1024 * 1024)               /* 2 MB  */
#define ZEND_MM_PAGE_SIZE  (4 * 1024)                      /* 4 KB  */
#define ZEND_MM_PAGES      (ZEND_MM_CHUNK_SIZE / ZEND_MM_PAGE_SIZE)  /* 512 */
#define ZEND_MM_FIRST_PAGE (1)
#define ZEND_MM_MAX_SMALL_SIZE      3072
#define ZEND_MM_MAX_LARGE_SIZE      (ZEND_MM_CHUNK_SIZE - (ZEND_MM_PAGE_SIZE * ZEND_MM_FIRST_PAGE))

2.3计算规格(bin_num)

我们发现在调用zend_mm_alloc_small时,使用到了ZEND_MM_SMALL_SIZE_TO_BIN,其定义了一个函数,用于将size转换为bin_num;即请求7字节时,实际需要分配8字节,bin_num=1;请求37字节时,实际需要分配40字节,bin_num=4;即根据请求的size计算满足条件的最小small内存规格的bin_num;

#define ZEND_MM_SMALL_SIZE_TO_BIN(size)  zend_mm_small_size_to_bin(size)
 
static zend_always_inline int zend_mm_small_size_to_bin(size_t size)
{
 
    unsigned int t1, t2;
 
    if (size <= 64) {
        /* we need to support size == 0 ... */
        return (size - !!size) >> 3;
    } else {
        t1 = size - 1;
        t2 = zend_mm_small_size_to_bit(t1) - 3;
        t1 = t1 >> t2;
        t2 = t2 - 3;
        t2 = t2 << 2;
        return (int)(t1 + t2);
        //看到这一堆t1,t2,脑子里只有一个问题:我是谁,我在哪,这是啥;
    }
}

1)先分析size小于64情况:看看small内存前8组大小定义,8,16,24,32,48,56,64;很简单,就是等差数列,递增8;所以对于每个size只要除以8就可以了(右移3位);但是对于size=8,16,24,32,40,48,56,64这些值,需要size-1然后除以8才满足;考虑到size=0的情况,于是有了(size - !!size) >> 3这个表达式;

2)当size大于64时,情况就复杂了:small内存的字节数变化为,64,80,96,112,128,160,192,224,256,320,384,448,512……;递增16,递增32,递增64……;

还是先看看二进制吧:

clipboard.png

我们将size每4个分为一组,第一组比特序列长度为7,第二组比特序列长度为8,……;(即我们可以根据比特序列长度获得sise属于哪一组;思考一下,递增16,32时,为什么只会加四次呢?)

那我们可以这么算:1)计算出size属于第几组;2)计算size在组内的偏移量;3)计算组开始位置。思路就是这样,但是计算方法并不统一,只要找规律计算出来即可。

//计算当前size属于哪一组;也就是计算比特序列长度;也就是计算最高位是1的位置;
 
//从低到高位查找也行,O(n)复杂度;使用二分查号,复杂度log(n)
 
//size最大为3072(不知道的回去看small内存宏定义);将size的二进制看成16比特的序列;
//先按照8二分,再按照4或12二分,再按照2/6/10/16二分……
 
//思路:size与255比较(0xff)比较,如果小于,说明高8位全是0,只需要在低8位查找即可;
//…………
 
/* higher set bit number (0->N/A, 1->1, 2->2, 4->3, 8->4, 127->7, 128->8 etc) */
static zend_always_inline int zend_mm_small_size_to_bit(int size)
{
    int n = 16;
    if (size <= 0x00ff) {n -= 8; size = size << 8;}
    if (size <= 0x0fff) {n -= 4; size = size << 4;}
    if (size <= 0x3fff) {n -= 2; size = size << 2;}
    if (size <= 0x7fff) {n -= 1;}
    return n;
}

2.4开始分配了

前面说过small空闲内存会形成链表,挂在zen_mm_heap字段free_slot[bin_num]上;

最初请求分配时,free_slot[bin_num]可能还没有初始化,指向null;此时需要向chunk分配若干页,将页分割为大小相同的内存块,形成链表,挂在free_slot[bin_num]

static zend_always_inline void *zend_mm_alloc_small(zend_mm_heap *heap, size_t size, int bin_num)
{
    //空闲链表不为null,直接分配
    if (EXPECTED(heap->free_slot[bin_num] != NULL)) {
        zend_mm_free_slot *p = heap->free_slot[bin_num];
        heap->free_slot[bin_num] = p->next_free_slot;
        return (void*)p;
    } else {
    //先分配页
        return zend_mm_alloc_small_slow(heap, bin_num;
    }
}
//分配页;切割;形成链表
static zend_never_inline void *zend_mm_alloc_small_slow(zend_mm_heap *heap, uint32_t bin_num)
{
    zend_mm_chunk *chunk;
    int page_num;
    zend_mm_bin *bin;
    zend_mm_free_slot *p, *end;
 
    //分配页(页数目是small内存宏定义第四列);放在下一节large内存分配讲解
    bin = (zend_mm_bin*)zend_mm_alloc_pages(heap, bin_pages[bin_num]);
 
    if (UNEXPECTED(bin == NULL)) {
        /* insufficient memory */
        return NULL;
    }
     
    //之前提过任何内存分配器都需要额外的数据结构记录每块内存的属性;分析发现PHP每个page的所有内存块属性都是相同的;且存储在zend_mm_chunk结构体的map字段(512个int)
    //bin即页的首地址;需要计算bin是当前chunk的第几页:1)得到chunk首地址;2)得到bin相对chunk首地址偏移量;3)除以页大小
    chunk = (zend_mm_chunk*)ZEND_MM_ALIGNED_BASE(bin, ZEND_MM_CHUNK_SIZE);
    page_num = ZEND_MM_ALIGNED_OFFSET(bin, ZEND_MM_CHUNK_SIZE) / ZEND_MM_PAGE_SIZE;
     
    //记录页属性;后面分析(对于分配的每个页都要记录属性)
    chunk->map[page_num] = ZEND_MM_SRUN(bin_num);
    if (bin_pages[bin_num] > 1) {
        uint32_t i = 1;
 
        do {
            chunk->map[page_num+i] = ZEND_MM_NRUN(bin_num, i);
            i++;
        } while (i < bin_pages[bin_num]);
    }
 
    //切割内存;形成链表(bin_data_size,bin_elements是上面介绍过的small内存相关数组)
    end = (zend_mm_free_slot*)((char*)bin + (bin_data_size[bin_num] * (bin_elements[bin_num] - 1)));
    heap->free_slot[bin_num] = p = (zend_mm_free_slot*)((char*)bin + bin_data_size[bin_num]);
    do {
        p->next_free_slot = (zend_mm_free_slot*)((char*)p + bin_data_size[bin_num]);
        p = (zend_mm_free_slot*)((char*)p + bin_data_size[bin_num]);
    } while (p != end);
 
    /* terminate list using NULL */
    p->next_free_slot = NULL;
 
    /* return first element */
    return (char*)bin;
}

2.5说说记录页属性的map

1)对任意地址p,如何计算页号?

地址p减去chunk首地址获得偏移量;偏移量除4K即可;问题是如何获得chunk首地址?我们看看源码:

chunk = (zend_mm_chunk*)ZEND_MM_ALIGNED_BASE(bin, ZEND_MM_CHUNK_SIZE);
page_num = ZEND_MM_ALIGNED_OFFSET(bin, ZEND_MM_CHUNK_SIZE) / ZEND_MM_PAGE_SIZE;
 
#define ZEND_MM_ALIGNED_OFFSET(size, alignment) \
    (((size_t)(size)) & ((alignment) - 1))
#define ZEND_MM_ALIGNED_BASE(size, alignment) \
    (((size_t)(size)) & ~((alignment) - 1))
#define ZEND_MM_SIZE_TO_NUM(size, alignment) \
    (((size_t)(size) + ((alignment) - 1)) / (alignment))

我们发现计算偏移量或chunk首地址时,需要两个参数:size,地址p;alignment,调用时传的是ZEND_MM_CHUNK_SIZE(2M);

其实PHP在申请chunk时,额外添加了一个条件:chunk首地址2M字节对齐;

clipboard.png

如图,2M字节对齐时,给定任意地址p,p的低21位即地址p相对于chunk首地址的偏移量;

那如何保证chunk首地址2M字节对齐呢?分析源码:

//chunk大小为size 2M;chunk首地址对齐方式 2M
static void *zend_mm_chunk_alloc_int(size_t size, size_t alignment)
{
    void *ptr = zend_mm_mmap(size);
 
    if (ptr == NULL) {
        return NULL;
    } else if (ZEND_MM_ALIGNED_OFFSET(ptr, alignment) == 0) { //2M对齐,直接返回
        return ptr;
    } else {
        size_t offset;
 
        //没有2M对齐,先释放,再重新分配2M+2M-4K空间
        //重新分配大小为2M+2M也是可以的(减4K是因为操作系统分配内存按页分配的,页大小4k)
        //此时总能定位一段2M的内存空间,且首地址2M对齐
        zend_mm_munmap(ptr, size);
        ptr = zend_mm_mmap(size + alignment - REAL_PAGE_SIZE);
 
        //分配了2M+2M-4K空间,需要释放前面、后面部分空间。只保留中间按2M字节对齐的chunk即可
        offset = ZEND_MM_ALIGNED_OFFSET(ptr, alignment);
        if (offset != 0) {
            offset = alignment - offset;
            zend_mm_munmap(ptr, offset);
            ptr = (char*)ptr + offset;
            alignment -= offset;
        }
        if (alignment > REAL_PAGE_SIZE) {
            zend_mm_munmap((char*)ptr + size, alignment - REAL_PAGE_SIZE);
        }
        return ptr;
    }
}
//理论分析,申请2M空间,能直接2M字节对齐的概率很低;但是实验发现,概率还是蛮高的,这可能与内核分配内存有关;

2)每个页都需要记录哪些属性?

chunk里的某个页,可以分配为large内存,large内存连续占多少个页;可以分配为small内存,对应的是哪种规格的small内存(bin_num)

//29-31比特表示当前页分配为small还是large
//当前页用于large内存分配
#define ZEND_MM_IS_LRUN                  0x40000000
//当前页用于small内存分配
#define ZEND_MM_IS_SRUN                  0x80000000
 
//对于large内存,0-9比特表示分配的页数目
#define ZEND_MM_LRUN_PAGES_MASK          0x000003ff
#define ZEND_MM_LRUN_PAGES_OFFSET        0
 
//对于small内存,0-4比特表示bin_num
#define ZEND_MM_SRUN_BIN_NUM_MASK        0x0000001f
#define ZEND_MM_SRUN_BIN_NUM_OFFSET      0
 
//count即large内存占了多少个页
#define ZEND_MM_LRUN(count)              (ZEND_MM_IS_LRUN | ((count) << ZEND_MM_LRUN_PAGES_OFFSET))
#define ZEND_MM_SRUN(bin_num)            (ZEND_MM_IS_SRUN | ((bin_num) << ZEND_MM_SRUN_BIN_NUM_OFFSET))

再回顾一下small内存30种规格的宏定义,bin_num=16、17、20-29时,需要分配大于1个页;此时不仅需要记录bin_num,还需要记录其对应的页数目

#define ZEND_MM_SRUN_BIN_NUM_MASK        0x0000001f
#define ZEND_MM_SRUN_BIN_NUM_OFFSET      0
 
#define ZEND_MM_SRUN_FREE_COUNTER_MASK   0x01ff0000
#define ZEND_MM_SRUN_FREE_COUNTER_OFFSET 16
 
#define ZEND_MM_NRUN_OFFSET_MASK         0x01ff0000
#define ZEND_MM_NRUN_OFFSET_OFFSET       16
 
//当前页分配为small内存;0-4比特存储bin_num;16-25存储当前规格需要分配的页数目;
#define ZEND_MM_SRUN_EX(bin_num, count)  (ZEND_MM_IS_SRUN | ((bin_num) << ZEND_MM_SRUN_BIN_NUM_OFFSET) |
        ((count) << ZEND_MM_SRUN_FREE_COUNTER_OFFSET))
 
//29-31比特表示同时属于small内存和large内存;0-4比特存储bin_num;16-25存储偏移量
//对于bin_num=29,需要分配3个页,假设为10,11,12号页
//map[10]=ZEND_MM_SRUN_EX(29,3);map[11]=ZEND_MM_NRUN(29,1);map[12]=ZEND_MM_NRUN(29,2);
#define ZEND_MM_NRUN(bin_num, offset)    (ZEND_MM_IS_SRUN | ZEND_MM_IS_LRUN | ((bin_num) << ZEND_MM_SRUN_BIN_NUM_OFFSET) |
        ((offset) << ZEND_MM_NRUN_OFFSET_OFFSET))

3.large内存分配:

需要从chunk中查找连续pages_count个空闲的页;zend_mm_chunk结构体的free_map为512个比特,记录着每个页空闲还是已分配;

以64位机器为例,free_map又被分为8组;每组64比特,看作uint32_t类型;

#define ZEND_MM_CHUNK_SIZE (2 * 1024 * 1024)               /* 2 MB  */
#define ZEND_MM_PAGE_SIZE  (4 * 1024)                      /* 4 KB  */
#define ZEND_MM_PAGES      (ZEND_MM_CHUNK_SIZE / ZEND_MM_PAGE_SIZE)  /* 512 */
 
typedef zend_ulong zend_mm_bitset;    /* 4-byte or 8-byte integer */
 
#define ZEND_MM_BITSET_LEN      (sizeof(zend_mm_bitset) * 8)       /* 32 or 64 */
#define ZEND_MM_PAGE_MAP_LEN    (ZEND_MM_PAGES / ZEND_MM_BITSET_LEN) /* 16 or 8 */
static void *zend_mm_alloc_pages(zend_mm_heap *heap, uint32_t pages_count)
{
    //获取main_chunk
    zend_mm_chunk *chunk = heap->main_chunk;
    uint32_t page_num, len;
    int steps = 0;
 
    //其实就是最佳适配算法
    while (1) {
        //free_pages记录当前chunk的空闲页数目
        if (UNEXPECTED(chunk->free_pages < pages_count)) {
            goto not_found;
        } else {
            /* Best-Fit Search */
            int best = -1;
            uint32_t best_len = ZEND_MM_PAGES;
 
            //从free_tail位置开始,后面得页都是空闲的
            uint32_t free_tail = chunk->free_tail;
            zend_mm_bitset *bitset = chunk->free_map;
            zend_mm_bitset tmp = *(bitset++);
            uint32_t i = 0;
            //从第一组开始遍历;查找若干连续空闲页;i实际每次递增64;
            //最佳适配算法;查找到满足条件的间隙,空闲页数目大于pages_count;
            //best记录间隙首位置;best_len记录间隙空闲页数目
            while (1) {
                //注意:(zend_mm_bitset)-1,表示将-1强制类型转换为64位无符号整数,即64位全1(表示当前组的页全被分配了)
                while (tmp == (zend_mm_bitset)-1) {
                    i += ZEND_MM_BITSET_LEN;
                    if (i == ZEND_MM_PAGES) {
                        if (best > 0) {
                            page_num = best;
                            goto found;
                        } else {
                            goto not_found;
                        }
                    }
                    tmp = *(bitset++); //当前组的所有页都分配了,递增到下一组
                }
                //每一个空闲间隙,肯定有若干个比特0,查找第一个比特0的位置:
                //假设当前tmp=01111111(低7位全1,高位全0);则zend_mm_bitset_nts函数返回8
                page_num = i + zend_mm_bitset_nts(tmp); 函数实现后面分析
                 
                //tmp+1->10000000;  tmp&(tmp+1)  其实就是把tmp的低8位全部置0,只保留高位
                tmp &= tmp + 1;
                 
                //如果此时tmp == 0,说明从第个页page_num到当前组最后一个页,都是未分配的;
                //否则,需要找出这个空闲间隙另外一个0的位置,相减才可以得出空闲间隙页数目
                while (tmp == 0) {
                    i += ZEND_MM_BITSET_LEN; //i+64,如果超出free_tail或者512,说明从page_num开始后面所有页都是空闲的;否则遍历下一组
                    if (i >= free_tail || i == ZEND_MM_PAGES) {
                        len = ZEND_MM_PAGES - page_num;
                        if (len >= pages_count && len < best_len) {   //从page_num处开始后面页都空闲,且剩余页数目小于已经查找到的连续空闲页数目,直接分配
                            chunk->free_tail = page_num + pages_count;
                            goto found;
                        } else {  //当前空闲间隙页不满足条件
                              
                            chunk->free_tail = page_num;
                            if (best > 0) { //之前有查找到空闲间隙符合分配条件
                                page_num = best;
                                goto found;
                            } else {  //之前没有查找到空闲页满足条件,说明失败
                                goto not_found;
                            }
                        }
                    }
                    tmp = *(bitset++); //遍历下一组
                }
                 
                //假设最初tmp=1111000001111000111111,tmp&=tmp+1后,tmp=1111000001111000 000000
                //上面while循环进不去;且page_num=7+i;
                //此时需从低到高位查找第一个1比特位置,为11,11+i-(7+i)=4,即是连续空闲页数目
                len = i + zend_ulong_ntz(tmp) - page_num;
                if (len >= pages_count) { //满足分配条件,记录
                    if (len == pages_count) {
                        goto found;
                    } else if (len < best_len) {
                        best_len = len;
                        best = page_num;
                    }
                }
                 
                //上面计算后tmp=1111000001111000 000000;发现这一组还有一个空闲间隙,拥有5个空闲页,下一个循环肯定需要查找出来;
                //而目前低10比特其实已经查找过了,那么需要将低10比特全部置1,以防再次查找到;
                //tmp-1:1111000001110111 111111; tmp |= tmp - 1:1111000001111111 111111
                tmp |= tmp - 1;
            }
        }
 
not_found:
        ………………
found:
     
    //查找到满足条件的连续页,设置从page_num开始pages_count个页为已分配
    chunk->free_pages -= pages_count;
    zend_mm_bitset_set_range(chunk->free_map, page_num, pages_count);
    //标志当前页用于large内存分配,分配数目为pages_count
    chunk->map[page_num] = ZEND_MM_LRUN(pages_count);
    //更新free_tail
    if (page_num == chunk->free_tail) {
        chunk->free_tail = page_num + pages_count;
    }
    //返回当前第一个page的首地址
    return ZEND_MM_PAGE_ADDR(chunk, page_num);
}
 
//4K大小的字节数组
struct zend_mm_page {
    char               bytes[ZEND_MM_PAGE_SIZE];
};
 
//偏移page_num*4K
#define ZEND_MM_PAGE_ADDR(chunk, page_num) \
    ((void*)(((zend_mm_page*)(chunk)) + (page_num)))

看看PHP是如何高效查找0比特位置的:依然是二分查找

static zend_always_inline int zend_mm_bitset_nts(zend_mm_bitset bitset)
{
    int n=0;
//64位机器才会执行
#if SIZEOF_ZEND_LONG == 8
    if (sizeof(zend_mm_bitset) == 8) {
        if ((bitset & 0xffffffff) == 0xffffffff) {n += 32; bitset = bitset >> Z_UL(32);}
    }
#endif
    if ((bitset & 0x0000ffff) == 0x0000ffff) {n += 16; bitset = bitset >> 16;}
    if ((bitset & 0x000000ff) == 0x000000ff) {n +=  8; bitset = bitset >>  8;}
    if ((bitset & 0x0000000f) == 0x0000000f) {n +=  4; bitset = bitset >>  4;}
    if ((bitset & 0x00000003) == 0x00000003) {n +=  2; bitset = bitset >>  2;}
    return n + (bitset & 1);
}

4.huge内存分配:

//
#define ZEND_MM_ALIGNED_SIZE_EX(size, alignment) \
    (((size) + ((alignment) - Z_L(1))) & ~((alignment) - Z_L(1)))
 
//会将size扩展为2M字节的整数倍;直接调用分配chunk的函数申请内存
//huge内存以n*2M字节对齐的
static void *zend_mm_alloc_huge(zend_mm_heap *heap, size_t size)
{
    size_t new_size = ZEND_MM_ALIGNED_SIZE_EX(size, MAX(REAL_PAGE_SIZE, ZEND_MM_CHUNK_SIZE));
     
    void *ptr = zend_mm_chunk_alloc(heap, new_size, ZEND_MM_CHUNK_SIZE);
    return ptr;
}

5.内存释放

ZEND_API void ZEND_FASTCALL _efree(void *ptr)
{
    zend_mm_free_heap(AG(mm_heap), ptr);
}
 
static zend_always_inline void zend_mm_free_heap(zend_mm_heap *heap, void *ptr)
{
    //计算当前地址ptr相对于chunk的偏移
    size_t page_offset = ZEND_MM_ALIGNED_OFFSET(ptr, ZEND_MM_CHUNK_SIZE);
 
    //偏移为0,说明是huge内存,直接释放
    if (UNEXPECTED(page_offset == 0)) {
        if (ptr != NULL) {
            zend_mm_free_huge(heap, ptr);
        }
    } else {
        //计算chunk首地址
        zend_mm_chunk *chunk = (zend_mm_chunk*)ZEND_MM_ALIGNED_BASE(ptr, ZEND_MM_CHUNK_SIZE);
        //计算页号
        int page_num = (int)(page_offset / ZEND_MM_PAGE_SIZE);
        //获得页属性信息
        zend_mm_page_info info = chunk->map[page_num];
 
        //small内存
        if (EXPECTED(info & ZEND_MM_IS_SRUN)) {
            zend_mm_free_small(heap, ptr, ZEND_MM_SRUN_BIN_NUM(info));
        }
        //large内存
        else /* if (info & ZEND_MM_IS_LRUN) */ {
            int pages_count = ZEND_MM_LRUN_PAGES(info);
             //将页标记为空闲
            zend_mm_free_large(heap, chunk, page_num, pages_count);
        }
    }
}

static zend_always_inline void zend_mm_free_small(zend_mm_heap *heap, void *ptr, int bin_num)
{
    zend_mm_free_slot *p;
    //插入空闲链表头部即可
    p = (zend_mm_free_slot*)ptr;
    p->next_free_slot = heap->free_slot[bin_num];
    heap->free_slot[bin_num] = p;
}


6.zend_mm_heap和zend_mm_chunk

PHP有一个全局唯一的zend_mm_heap,其是zend_mm_chunk一个字段;

zend_mm_chunk至少需要空间2k+;和zend_mm_chunk存储在哪里?

这两个结构体其实是存储在chunk的第一个页,即chunk的第一个页始终是分配的,且用户不能申请的;

申请的多个chunk之间是形成双向链表的;如下图所示:

clipboard.png

static zend_mm_heap *zend_mm_init(void)
{
    //将分配的2M空间,强制转换为zend_mm_chunk*;并初始化zend_mm_chunk结构体
    zend_mm_chunk *chunk = (zend_mm_chunk*)zend_mm_chunk_alloc_int(ZEND_MM_CHUNK_SIZE, ZEND_MM_CHUNK_SIZE);
    zend_mm_heap *heap;
 
    heap = &chunk->heap_slot;
    chunk->heap = heap;
    chunk->next = chunk;
    chunk->prev = chunk;
    chunk->free_pages = ZEND_MM_PAGES - ZEND_MM_FIRST_PAGE;
    chunk->free_tail = ZEND_MM_FIRST_PAGE;
    chunk->num = 0;
    chunk->free_map[0] = (Z_L(1) << ZEND_MM_FIRST_PAGE) - 1;
    chunk->map[0] = ZEND_MM_LRUN(ZEND_MM_FIRST_PAGE);
    heap->main_chunk = chunk;
    heap->cached_chunks = NULL;
    heap->chunks_count = 1;
    heap->peak_chunks_count = 1;
    heap->cached_chunks_count = 0;
    heap->avg_chunks_count = 1.0;
    heap->last_chunks_delete_boundary = 0;
    heap->last_chunks_delete_count = 0;
    heap->huge_list = NULL;
    return heap;
}

7. PHP内存管理器初始化流程:

PHP虚拟机什么时候初始化内管理器呢?heap与chunk又是什么时候初始化呢?
下图为PHP内存管理器初始化流程;
有兴趣同学可以在相关函数处加断点,跟踪内存管理器初始化流程;

clipboard.png

8. PHP内存管理总结:

1)需要明白一点:任何内存分配器都需要额外的数据结构来记录内存的分配情况;

2)内存池是代替直接调用malloc/free、new/delete进行内存管理的常用方法;内存池中空闲内存块组织为链表结果,申请内存只需要查找空闲链表即可,释放内存需要将内存块重新插入空闲链表;

3)PHP采用预分配内存策略,提前向操作系统分配2M字节大小内存,称为chunk;同时将内存分配请求根据字节大小分为small、huge、large三种;

4)small内存,采用“分离存储”思想;将空闲内存块按照字节大小组织为多个空闲链表;

5)large内存每次回分配连续若干个页,采用最佳适配算法;

6)huge内存直接使用mmap函数向操作系统申请内存(申请大小是2M字节整数倍);

7)chunk中的每个页只会被切割为相同规格的内存块;所以不需要再每个内存块添加头部,只需要记录每个页的属性即可;

8)如何方便根据地址计算当前内存块属于chunk中的哪一个页?PHP分配的chunk都是2M字节对齐的,任意地址的低21位即是相对chunk首地址,除以页大小则可获得页号;

结束语

本文首先简单介绍了计算机操作系统内存相关知识,然后描述了malloc内存分配器设计思路,以及内存池的简单理论;最后从源码层面详细分析了PHP内存管理器的实现;相信通过这篇文章,大家对内存管理页有了一定的了解;
对于PHP源码有兴趣的同学,欢迎加入我们的微信群,我们可以一起探讨与学习;

clipboard.png

同时欢迎关注微博:
图片描述

查看原文

赞 48 收藏 43 评论 2

书旅 发布了文章 · 2020-12-09

数据结构与算法系列之散列表(一)(GO)

关于散列表的代码实现及下边实践部分的代码实现均可从我的Github获取(欢迎star^_^)

散列思想

概念

散列表(Hash Table),也可以叫它哈希表或者Hash表

散列表用的是数组支持按照下标随机访问数据的特性,所以散列表其实就是数组的一种扩展,由数组演化而来。可以说,如果没有数组,就没有散列表

举例

假设全校有1000名学生,为了方便记录他们的期末成绩,会给每个学生一个编号,编号从1~1000。现在如果要实现通过编号来找到具体的学生

可以把这1000个学生的信息放在数组里。编号为1的学生,放到数组中下标为1的位置;编号为2的学生,放到数组中下标为2的位置。以此类推,编号为k的学生放到数组中下标为k的位置

因为编号跟数组下标一一对应,当我们需要查询编号为x的学生的时候,只需要将下标为x的数组元素取出来就可以了,时间复杂度就是O(1)

实际上,这个例子已经用到了散列的思想。在这个例子里,编号是自然数,并且与数组的下标形成一一映射,所以利用数组支持根据下标随机访问的特性,查找的时间复杂度是O(1) ,就可以实现快速查找编号对应的学生信息

但是,上边这个例子用到的散列思想不够明显,改一下

假设编号不能设置得这么简单,要加上年级、班级这些更详细的信息,所以这里把编号的规则稍微修改了一下,用8位数字来表示。比如05110067,其中,前两位05表示年级,中间两位11表示班级,最后四位还是原来的编号1到1000。这个时候该如何存储学生信息,才能够支持通过编号来快速查找学生信息呢?

思路还是跟前面类似。尽管不能直接把编号作为数组下标,但可以截取编号的后四位作为数组下标,来存取学生信息数据。当通过编号查询学生信息的时候,用同样的方法,取编号的后四位,作为数组下标,来读取数组中的数据

这就是典型的散列思想。其中,学生的编号叫作键(key)或者关键字。用它来标识一个学生。把学生编号转化为数组下标的映射方法就叫作散列函数(或“Hash函数”“哈希函数”),而散列函数计算得到的值就叫作散列值(或“Hash 值”“哈希值”)

总结

散列表用的就是数组支持按照下标随机访问的时候,时间复杂度是O(1)的特性。通过散列函数把元素的键值映射为下标,然后将数据存储在数组中对应下标的位置。当按照键值查询元素时,用同样的散列函数,将键值转化数组下标,从对应的数组下标的位置取数据

散列函数

概念

散列函数,顾名思义,它是一个函数。可以把它定义成hash(key) ,其中key表示元素的键值,hash(key)的值表示经过散列函数计算得到的散列值

在上边的例子中,编号就是数组下标,所以hash(key)就等于 key。改造后的例子,写成散列函数就像下边这样

func hash(key string) int {
    hashValue,_ := strconv.Atoi(key[len(key)-4:])

    return hashValue
}

散列函数基本要求

上边的的例子,散列函数比较简单,也比较容易想到。但是,如果学生的编号是随机生成的6位数字,又或者用的是a到z之间的字符串,这种情况,散列函数就会复杂一些

散列函数设计的基本要求

  • 散列函数计算得到的散列值是一个非负整数
  • 如果key1 = key2,那hash(key1) == hash(key2)
  • 如果key1 ≠ key2,那hash(key1) ≠ hash(key2)

第一点理解起来应该没有任何问题。因为数组下标是从0开始的,所以散列函数生成的散列值也要是非负整数。第二点也很好理解。相同的key,经过散列函数得到的散列值也应该是相同的

第三点理解起来可能会有问题。这个要求看起来合情合理,但是在真实的情况下,要想找到一个不同的key对应的散列值都不一样的散列函数,几乎是不可能的。即便像业界著名的MD5、SHA、CRC等哈希算法,也无法完全避免这种散列冲突。而且,因为数组的存储空间有限,也会加大散列冲突的概率

所以,几乎无法找到一个完美的无冲突的散列函数,即便能找到,付出的时间成本、计算成本也是很大的,所以针对散列冲突问题,需要通过其他途径来解决

散列冲突

开放寻址法

开放寻址法的核心思想是,如果出现了散列冲突,就重新探测一个空闲位置,将其插入
重新探测一个空闲位置的方法有好几个,这里以线性探测举例

当往散列表中插入数据时,如果某个数据经过散列函数散列之后,存储位置已经被占用了,就从当前位置开始,依次往后查找,看是否有空闲位置,直到找到为止。看下图

从图中可以看出,散列表的大小为10,在元素x插入散列表之前,已经有6个元素插入到散列表中。x经过hash算法之后,被散列到下标为7的位置,但是这个位置已经有数据了,所以就产生了冲突。于是就顺序地往后一个一个找,看有没有空闲的位置,遍历到尾部都没有找到空闲的位置,于是再从表头开始找,直到找到空闲位置2,于是将其插入到这个位置

在散列表中查找元素的过程类似插入过程。通过散列函数求出要查找元素的键值对应的散列值,然后比较数组中下标为散列值的元素和要查找的元素。如果相等,则说明就是我们要找的元素;否则就顺序往后依次查找。如果遍历到数组中的空闲位置,还没有找到,就说明要查找的元素并没有在散列表中

散列表和数组一样,也支持插入、查找、删除操作,但是对于线性探测方法解决散列冲突,在进行删除操作时比较特殊,不能单纯地把要删除的元素设置为空

上边在说散列表的查找操作时,通过线性探测的方式找到一个空闲位置,然后就认定散列表中不存在该数据。如果说这个空闲位置是后来删除的,就会导致原来的线性探测有问题,可能本来存在的数据,以为不存在了

这种情况下,就需要将删除的元素加一个删除的标记。在进行线性探测的时候,如果遇到删除标记的元素,则继续向下探测

小伙伴肯定已经看出问题了,当散列表中插入的数据越来越多时,散列冲突发生的可能性就会越来越大,空闲位置会越来越少,线性探测的时间就会越来越久。极端情况下,可能需要探测整个散列表,所以最坏情况下的时间复杂度为O(n)。同理,在删除和查找时,也有可能会线性探测整张散列表,才能找到要查找或者删除的数据

对于开放寻址冲突解决方法,除了线性探测方法之外,还有另外两种比较经典的探测方法,二次探测(Quadratic probing)和双重散列(Double hashing)

二次探测

二次探测跟线性探测很像,线性探测每次探测的步长是1,它探测的下标序列就是hash(key)+0,hash(key)+1,hash(key)+2……而二次探测探测的步长就变成了原来的“二次方”,它探测的下标序列是hash(key)+0,hash(key)+1^2,hash(key)+2^2,hash(key)+3^2……

双重散列

双重散列意思就是不仅要使用一个散列函数。使用一组散列函数 hash1(key),hash2(key),hash3(key)……先用第一个散列函数,如果计算得到的存储位置已经被占用,再用第二个散列函数,依次类推,直到找到空闲的存储位置

开放寻址法总结

不管采用哪种探测方法,当散列表中空闲位置不多的时候,散列冲突的概率就会大大提高。为了尽可能保证散列表的操作效率,一般情况下,会尽可能保证散列表中有一定比例的空闲槽位。用装载因子(load factor)来表示空位的多少

装载因子的计算公式

散列表的装载因子 = 填入表中的元素个数 / 散列表的长度

装载因子越大,说明空闲位置越少,冲突越多,散列表的性能会下降

链表法

链表法是一种更加常用的散列冲突解决办法,相比开放寻址法,它比较简单。在散列表中,每个“桶(bucket)”或者“槽(slot)”会对应一条链表,所有散列值相同的元素都放到相同槽位对应的链表中

当插入的时候,只需要通过散列函数计算出对应的散列槽位,将其插入到对应链表中即可,所以插入的时间复杂度是O(1)。当查找、删除一个元素时,同样通过散列函数计算出对应的槽,然后遍历链表查找或者删除

对于查找和删除操作,时间复杂度跟链表的长度k成正比,也就是 O(k)。对于散列比较均匀的散列函数来说,理论上讲,k=n/m,其中n表示散列中数据的个数,m表示散列表中“槽”的个数

实践

假设我们有10万条URL访问日志,如何按照访问次数给URL排序?

遍历10万条数据,以URL为key,访问次数为value,存入散列表,同时记录下访问次数的最大值K,时间复杂度O(N)

如果K不是很大,可以使用桶排序,时间复杂度O(N)。如果 K 非常大(比如大于10万),就使用快速排序,复杂度O(NlogN)

由于文章篇幅的原因,代码实现,我放在了github上,需要的可以自取(GO实现)

有两个字符串数组,每个数组大约有10万条字符串,如何快速找出两个数组中相同的字符串?

以第一个字符串数组构建散列表,key 为字符串,value 为出现次数。再遍历第二个字符串数组,以字符串为 key 在散列表中查找,如果 value 大于零,说明存在相同字符串。时间复杂度 O(N)

查看原文

赞 0 收藏 0 评论 0

书旅 发布了文章 · 2020-12-03

数据结构与算法系列之跳表(GO)

详细了解跳表

前边的一篇文章中分享了二分查找算法,里边有说到二分查找算法依赖数组的随机访问特性,只能用数组来实现。如果数据存储在链表中就没法用二分查找算法了

本篇文章分享的「跳表」,可以实现类似二分的查找算法,时间复杂度也是「O(logn)」

假设有一个有序的单链表,如果想从该链表中查找某一个数据,只能从头到尾的遍历查找,它的时间复杂度是O(n)。如何提高查找的效率?

假设我像下图这样,在原来的单链表上增加一级索引,每两个节点取一个结点到「索引层」。其中down为指向下一级节点的指针

假设现在需要查找【16】这个节点。可以先遍历索引层节点,当遍历到【13】这个节点时,发现下一个节点为【17】,那么我们要找的节点【16】肯定就在它们中间。此时,通过索引节点【13】的down指针,下降到原始链表层中继续遍历,此时只需要再遍历两个节点就找到了我们要查找的【16】。如果直接在原始链表中查找【16】,需要遍历10个结点,现在只需要遍历7个结点

从上边可以发现,加了一层索引之后,查找一个节点需要遍历的节点数减少了,也就意味着查找的效率提高了,如果我们增加更多的索引层,效率会不会提高更多?

假设现在在原来的一级索引上边按同样的方法,再增加一层索引,如果再查【16】这个节点,只需要遍历6个结点了。查找一个节点需要遍历的节点又减少了

上边的例子中,原始链表的节点数量并不多,每增加一层索引,查询效率提高的并不明显,下边假设原始链表中有64个节点,建立5级索引

从图中可以看出,原来没有索引的时候,查找【62】这个节点需要遍历62个节点,现在只需要遍历11个节点,速度提高了很多。当链表的长度n比较大时,比如1000、10000的时候,在构建索引之后,查找效率的提升就会非常明显。「这种链表加多级索引的结构,就是跳表」

跳表的时间复杂度

如果链表里有n个结点,可以有多少级索引?

按照上边例子中的那种方式,每两个结点会抽出一个结点作为上一级索引的结点,那第一级索引的结点个数大约就是n/2,第二级索引的结点个数大约就是n/4,第三级索引的结点个数大约就是n/8,依次类推,也就是说,第k级索引的结点个数是第k-1级索引的结点个数的1/2,那第k级索引结点的个数就是 n/(2^k)

假设索引有h级,最高级的索引有2个结点。通过上面的公式,可以得到n/(2^h)=2,从而求得 h=log2n-1(2为底)。如果包含原始链表这一层,整个跳表的高度就是log2n(2为底)。「在跳表中查询某个数据的时候,如果每一层都要遍历m个结点,那在跳表中查询一个数据的时间复杂度就是O(m*logn)」

这个m的值是多少?按照上边的例子中这种索引结构,我们每一级索引都最多只需要遍历3个结点,也就是说m=3,解释一下为啥是3

假设要查找的数据是x,在第k级索引中,我们遍历到y结点之后,发现x大于y,小于后面的结点z,所以我们通过y的 down 指针,从第k级索引下降到第k-1 级索引。在第k-1级索引中,y和 z之间只有3个结点(包含 y 和 z),所以,我们在k-1级索引中最多只需要遍历3个结点,依次类推,每一级索引都最多只需要遍历3个结点

通过上面的分析,得到m=3,所以「在跳表中查询任意数据的时间复杂度就是O(logn)」。这个查找的时间复杂度跟二分查找是一样的。换句话说,其实是基于单链表实现了二分查找。不过,天下没有免费的午餐,这种查询效率的提升,前提是建立了很多级索引,是一种空间换时间的思路

跳表的空间复杂度分析

假设原始链表大小为n,那第一级索引大约有n/2个结点,第二级索引大约有n/4个结点,以此类推,每上升一级就减少一半,直到剩下2个结点。如果我们把每层索引的结点数写出来,就是一个等比数列

`n/2, n/4, n/8,...,8, 4, 2
`

这几级索引的结点总和就是n/2+n/4+n/8…+8+4+2=n-2。所以,「跳表的空间复杂度是 O(n)」。也就是说,如果将包含n个结点的单链表构造成跳表,我们需要额外再用接近n个结点的存储空间

有没有办法降低索引占用的内存空间呢?

降低跳表空间复杂度的方法

前面都是每两个结点抽一个结点到上级索引,如果我们每三个结点或五个结点,抽一个结点到上级索引,就不用那么多索引结点了

从图中可以看出,第一级索引需要大约n/3个结点,第二级索引需要大约n/9个结点。每往上一级,索引结点个数都除以3。为了方便计算,假设最高一级的索引结点个数是1。我们把每级索引的结点个数都写下来,也是一个等比数列

`n/3, n/9, n/27, ... , 9, 3, 1
`

通过等比数列求和公式,总的索引结点大约就是n/3+n/9+n/27+…+9+3+1=n/2。尽管空间复杂度还是 O(n),但比上面的每两个结点抽一个结点的索引构建方法,要减少了一半的索引节点存储空间

实际上,在平时开发中,不必太在意索引占用的额外空间。在数据结构和算法中,习惯性地把要处理的数据看成「整数」,但是在实际的开发中,原始链表中存储的有可能是「很大的对象」,而索引结点只需要「存储关键值」和几个指针,并不需要存储对象,「所以当对象比索引结点大很多时,那索引占用的额外空间就可以忽略了」

跳表操作

跳表是个「动态数据结构」,不仅支持查找操作,还支持动态的插入、删除操作,而且插入、删除操作的时间复杂度也是「O(logn)」

插入

在单链表中,一旦定位好要插入的位置,插入结点的时间复杂度是很低的,就是 O(1)。但是,为了保证原始链表中数据的有序性,需要先找到要插入的位置,这个查找操作就会比较耗时

对于纯粹的单链表,需要遍历每个结点,来找到插入的位置。但是,对于跳表来说,查找某个节点的时间复杂度是 O(logn),所以这里查找某个数据应该插入的位置,方法也是类似的,时间复杂度也是O(logn)

删除

「如果要删除的结点在索引中有出现,除了要删除原始链表中的结点,还要删除索引中的」。因为单链表中的删除操作需要拿到要删除结点的前驱结点,然后通过指针操作完成删除。所以在查找要删除的结点的时候,一定要获取前驱结点。当然,如果用的是双向链表,就不需要考虑这个问题了

索引动态更新

当不停地往跳表中插入数据时,如果不更新索引,就有可能出现某2个索引结点之间数据非常多的情况。极端情况下,跳表还会退化成单链表

作为一种动态数据结构,它需要某种手段来维护索引与原始链表大小之间的平衡,也就是说,如果链表中结点多了,索引结点就相应地增加一些,避免复杂度退化,以及查找、插入、删除操作性能下降

「后边会分享到的红黑树、AVL树这样的平衡二叉树,它们是通过左右旋的方式保持左右子树的大小平衡」,而跳表是通过「随机函数」来维护前面提到的“平衡性”

当我们往跳表中插入数据的时候,可以选择同时将这个数据插入到部分索引层中。如何选择加入哪些索引层,就是随机函数要干的事情

通过一个随机函数,来决定将这个结点插入到哪几级索引中,比如随机函数生成了值K,那就将这个结点添加到「第一级到第K级」这K级索引中

随机函数的选择很有讲究,从概率上来讲,能够保证跳表的索引大小和数据大小平衡性,不至于性能过度退化

跳表的应用

「为什么Redis要用跳表来实现有序集合,而不是红黑树?」

Redis中的有序集合是通过跳表来实现的,严格点讲,其实还用到了「散列表」。后边的文章会分享到散列表,所以现在暂且忽略这部分。如果你了解Redis中的有序集合,它支持的核心操作主要有下面这几个

  • 插入一个数据;
  • 删除一个数据;
  • 查找一个数据;
  • 按照区间查找数据(比如查找值在 [100, 356] 之间的数据);
  • 迭代输出有序序列

其中,插入、删除、查找以及迭代输出有序序列这几个操作,红黑树也可以完成,时间复杂度跟跳表是一样的。但是,「按照区间来查找数据这个操作,红黑树的效率没有跳表高」

对于按照区间查找数据这个操作,跳表可以做到O(logn)的时间复杂度定位区间的起点,然后在原始链表中顺序往后遍历就可以了。这样做非常高效

Redis之所以用跳表来实现有序集合,还有其他原因,比如,跳表更容易代码实现。虽然跳表的实现也不简单,但比起红黑树来说还是好懂、好写多了,而简单就意味着可读性好,不容易出错。还有,跳表更加灵活,它可以通过改变索引构建策略,有效平衡执行效率和内存消耗

不过,跳表也不能完全替代红黑树。因为红黑树比跳表的出现要早一些,很多编程语言中的Map类型都是通过红黑树来实现的。做业务开发的时候,直接拿来用就可以了,不用费劲自己去实现一个红黑树,但是跳表并没有一个现成的实现,所以在开发中,如果你想使用跳表,必须要自己实现

查看原文

赞 0 收藏 0 评论 0

书旅 发布了文章 · 2020-11-23

LeetCode069-x的平方根-easy

标签:二分
题目:x的平方根
题号:69
题干:实现 int sqrt(int x) 函数。计算并返回 x 的平方根,其中 x 是非负整数。由于返回类型是整数,结果只保留整数的部分,小数部分将被舍去

示例1:
输入: 4
输出: 2

示例2:
输入: 8
输出: 2
解释: 8的平方根是 2.82842..., 由于返回类型是整数,小数部分将被舍去

原题比较简单,因此这里做简单的变形,求x的平方根,要求可以获取指定精度的结果

示例:
输入:8 0.000001
输出:2.828427
说明:0.000001表示精确到小数点后六位

思路:

  • 要求x的平方根,最容易想到的就是从1到x,一个一个的试,这种方法的时间复杂度是O(n),这不是我们想要的
  • 二分查找算法,显然是用来查找的算法,我们的目的也算是查找。如果你看过我的上一篇二分查找的文章,里边有说到什么情况下会想到用二分查找,比如我们要查找的一系列数是有序的等,我们要求x的平方根,那肯定在[1, x]这个区间找(x>1),它显然是有序的。这自然 会想到用二分来查找
  • 使用二分查找算法,需要两个游标low和high。需要考虑他们的初始值是什么?以及当mid不满足时,low和hight如何变化?
  • 既然是求x的平方根,x的值有两种情况。第一种是x<1,这种情况,我们要求的结果肯定在[0, 1]这区间内,所以就可以初始化low = 0,hight=1,那mid就为(low+hight)/2
  • x的第二种情况就很简单了,当x>1时,它的平方根的值肯定在[1, n]区间内,所以low = 1, high=x,mid = (low+hight)/2
  • 不难想到,当x-mid*mid < 0时,说明mid太大,那此时我们就应该在[1, mid]之间找,即,此时让hight=mid-1
  • 如果x-midmid > 0,这时要考虑x-midmid是否大于我们要求的精度,如果大于这个精度,那此时low = mid+1
  • 有了以上这些条件,基本上这道题就出来了。如果你按照上边的思路把代码写出来之后会发现是有问题的,当x<1的时候程序就不能正常运行了。原因是low和high变化的时候,如果x<1的时候,结果肯定是小于1的,如果直接让high或low为mid加1或减1肯定就不对了
  • 因此,当x-mid*mid < 0时,应该让high=(mid+high)/2

代码实现


func SolutionSqrt(num float64, precision float64) float64 {
  if num < 0 {
    fmt.Println("参数不合法")
    return -1.000
  }

  var low,high float64
  if num > 1 {
    low = 1
    high = num
  } else {
    low = num
    high = 1
  }

  return Sqrt(num, low, high, precision)
}

func Sqrt(num float64, low float64, high float64, precision float64) float64 {
  mid := (low+high) / 2

  if num - (mid * mid) < 0 {
    return Sqrt(num, low, (mid+high)/2, precision)
  } else {
    if num - (mid * mid) > precision {
      return Sqrt(num, (low + mid)/2, high, precision)
    }

    return mid
  }
}
查看原文

赞 0 收藏 0 评论 0

书旅 关注了用户 · 2020-11-23

LNMPRG源码研究 @php7internal

一群热爱代码的人 研究Nginx PHP Redis Memcache Beanstalk 等源码 以及一群热爱前端的人
希望交流的朋友请加微信 289007301 注明:思否 拉到交流群,也可关注公众号:LNMPRG源码研究

《PHP7底层设计与源码分析》勘误https://segmentfault.com/a/11...

《Redis5命令设计与源码分析》https://item.jd.com/12566383....

景罗 陈雷 李乐 黄桃 施洪宝 季伟滨 闫昌 李志 王坤 肖涛 谭淼 张仕华 方波 周生政 熊浩含 张晶晶(女) 李长林 朱栋 张晶晶(男) 陈朝飞 巨振声 杨晓伟 闫小坤 韩鹏 夏达 周睿 李仲伟 张根红 景罗 欧阳 孙伟 李德 twosee

关注 11685

书旅 赞了文章 · 2020-11-23

【PHP7底层设计与源码分析】部分勘误

1、序

clipboard.png

zal 改为 zval
2、33页
从图3-1中我们看出,虽然char a只占了1字节,int b只占了4字节,但是long c并不是紧跟着b,而是根据8字节对齐后,c和b之间空了3字节
改为
从图3-1中我们看出,虽然char a只占了1字节,int b只占了4字节,但是b并不是紧跟着a,而是根据8字节对齐后,a和b之间空了3字节

3、图4-6 动态字符串赋值后$a 与 $b 关系图
更正为:

clipboard.png

4、图4-7 常量字符串赋值后$a 与 $b 关系图
更正为:

clipboard.png

5、图4-9 引用类型$a 与 $b 关系图
更正为:

clipboard.png

6、图4-10 copy on write过程示意图
更正为:

clipboard.png

7、图4-11 整形转成字符串
更正为:

clipboard.png

8、图4-13 opcode组装中字符串处理示意图
更正为:

clipboard.png

9、图9-4替换为下图:

clipboard.png

10、58页 图3-17下面的代码修改为: 
代码更正为
for($i = 0; $i <= 10002; $i++){
$a[$i] = array($i."_string");
$a[$i][] = &$a[$i];
unset($a[$i]);
}

11、图3-4 PHP5中_zval_struct的大小
更正为:


clipboard.png

12、图3-5 PHP5中_zval_struct实际大小
更正为:


clipboard.png

13、图3-6 PHP5中变量实际占用的内存大小
更正为:


clipboard.png

14、图3-16 gc_globals的结构
更正为:


clipboard.png
15、4.2.2节 示例2代码有一处错误,更改前为:
图片描述
https://segmentfault.com/img/...
clipboard.png

更改后为:
图片描述
https://segmentfault.com/img/...
clipboard.png

16、
120页和122页代码修改为:

for($i=0;$i<4;$i++){
   $arr[$i] = 1;//packed array
}

以下是读者赵禹反馈, 感谢赵禹!

17、第4章 字符串:页码83页 php_request_shutdown方法名写成了 php_request_shotdow。

18、第6章 面向对象 : 页码138页,6.1.3接口中接口类可以通过extends继承,写成了 extend继承。

以下是读者Rai4over反馈:
19、 第108页,示例代码为:

$arr[] = 'foo';

改为

$a[] = 'foo';

感谢读者Rai4over

查看原文

赞 17 收藏 10 评论 20

认证与成就

  • 获得 11 次点赞
  • 获得 5 枚徽章 获得 0 枚金徽章, 获得 1 枚银徽章, 获得 4 枚铜徽章

擅长技能
编辑

开源项目 & 著作
编辑

(゚∀゚ )
暂时没有

注册于 2020-03-10
个人主页被 2.9k 人浏览