2021年10月11日星期一

IO性能相关

 SSD性能

  1. 固态硬盘有逻辑地址和物理地址的关联系统,所以不管顺序或者随机写都没有寻址时间,都是顺序写入nand。反复更新热点数据nand也会被均匀消耗。
  2. 没有读改写的过程,写入都是先将数据写入新的物理地址,再将原来的地址标为无效。
  3. ssd已经写入过数据的块需要擦除才能再次写入,类似gc的过程。随机写的数据擦除难度要大于顺序写。
  4. 队列深度,端口队列中等待服务的I/O请求数量,有点类似于网络服务中的缓存队列。队列深度和多线程还是有区别,单线程的时候,即使队列深度大于1,但每个访问请求的寻址和传输都是串行的,也就是必须先寻址然后才能传输。而多线程的时候,不同线程的这两步是可以并行的。
  5. ssd的顺序访问的定义,如果 I/O 操作开始的逻辑块地址(LBA)直接跟着前一个 I/O 操作的最后LBA,则称值为顺序访问
  6. 即使ssd随机访问也比顺序访问慢。原因是随机读不能利用预读功能提前缓存数据,每次 IO 需要重新定位物理地址,随机写造成大量磁盘碎片,极大地增加了垃圾回收的压力,小数据量的随机写无法利用 SSD 内置的并发能力
  7. ssd多线程随机读性能很好,某些时候甚至接近顺序读,因为ssd芯片本来就支持并发处理,顺序读的提前预测地址的能力相当于被多线程同时传入多个地址实现了。多线程随机写在磁盘充足的情况下也是同理,但是一旦gc性能就下来了,所以控制磁盘使用量也是一种优化手段。


参考链接 

写放大

不能原地更新只能先擦除再写入,写入是页为单位擦除只能块(很多页)为单位,如果一个块上面部分是有效数据部分要擦除只能把有效数据挪到其它块然后整块擦除,写放大就出来了。擦除过程类似GC,空余空间越多越容易腾挪,写放大就相对较小,所以不要把SSD写太满。

高延迟网络优化

TCP BBR

  1. 基于tcp的拥塞控制算法,在4.9以上的linux直接通过参数配置就可以使用
  2. 传统拥塞算法会不断增加窗口直到把带宽占满buffer占满直到丢包,丢包之后又会迅速降低发送速率。导致两个问题,高延迟网络往往丢包率高-不仅仅是buffer占满的丢包所以经常降低发送窗口导致低带宽利用。需要占满带宽和buffer来探测带宽导致高延迟。
  3. bbr解决方案关键点在于不用丢包判断带宽而是直接通过确认包来判断,慢启动发现带宽不再增加后不会进入占满buffer阶段。
  4. 网络链路上能容纳的数据包数量 = 链路带宽 × 往返延迟,所以还需要探测延迟,而buffer较满的时候延迟会有偏差,所以bbr会定时有低频率发包估算延迟的阶段。
参考链接

KCP

  1. 通常基于udp,实现了tcp的可靠传输,顺序,流控等等
  2. 选择性重传而不是tcp的全部重传,快速重传而不是等超时,立即ack而不是延时ack,非退让流控可以直接占满带宽,这几个是快的原因。如果丢包率高,重传应该对整体速度影响较大,快重传很有意义。
  3. 缺点是两端要安装额外的客户端,有额外的10%-20%的带宽浪费,另外主要应用好像在游戏,视频领域
参考链接




2021年8月22日星期日

InnoDB总结

最近读了一本不错的讲mysql的书MySQL是怎样运行的,借这个契机总结一下自己的InnoDB相关的知识。

MySQL整体架构

 

























关注的第一个问题,数据记录是怎么存储的?


表空间和表

一个数据库对应一个目录




























表结构存储

表名.frm

表数据存储

1.使用系统表空间 - 所有数据存储在指定文件(一个或多个)自动扩展大小
2.使用独立表空间 - 为每个表生成“表名.ibd ”文件,ibd文件存储表中的数据和索引

表空间结构(数据文件)

从大到小的逻辑概念是,表空间->段(segment)->区(extent)->页->记录。大家熟知的常识是数据被组织成一颗b+ tree,为了优化单次io的效率,引入了页的概念,io以页为单位。一个表可能有很多页,为了范围扫描的时候尽量是顺序io,引入了区的概念,区里面的页面是连续的。b+ tree的内节点和叶子节点如果混放,也可能会破坏顺序io,所以又引入段的概念,内节点是一个段,叶子节点是一个段。不过还有其他类型的段比如回滚段。

下面图中FSP_HDR描述表空间属性和本组256个区的属性,XDES描述本组256个区的属性,INODE描述段的属性














上面的图是独立表空间的结构,系统表空间的结构和独立表空间基本类似,只不过由于整个MySQL进程只有一个系统表空间,在系统表空间中会额外记录一些有关整个系统信息的页面,所以会比独立表空间多出一些记录这些信息的页面。

段结构

段不对应表空间中某一个连续的物理区域,而是一个逻辑上的概念,由若干个零散的页面以及一些完整的区组成。























上图是段属性描述结构

插入数据的时候需要,段->区->页,寻找一个页来插入记录。为了存储效率减少碎片会把区分成Free, Not Full, Full 几种类型,然后用链表串起来,用于这几个链表定位的基础节点就是上图蓝色部分。段中完整的区之外零散的页面由灰色部分管理,描述的是页面的页号。

区结构

对于16KB的页来说,连续的64个页就是一个区,也就是说一个区默认占用1MB空间大小。不论是系统表空间还是独立表空间,都可以看成是由若干个区组成的,每256个区被划分成一组

















对应段里面对区的管理,区被组织成链表所以有List Node结构。Page State Bitmap表示页面是否空闲的状态。

页结构

出于io效率考虑,页是mysql一次io操作的最小单位,而不是记录,页的大小一般是16k。
























1.File Header存放checksum,页号,页类型等页的全局信息,最重要的是会存放上一页和下一页的页号这样就组成了b+ tree需要的链表结构

2.Page Header存放页面状态,比如记录数量,还未使用的最小地址,页面在b+ tree中的层级等

3.File Trailer用来做页面完整性校验,保证刷盘时没有出意外

4.Infimum+supremum存放最大最小两条虚拟记录

5.User Records数据记录存入的过程就是不断找Free Space申请空间的过程















每条记录之间也会形成链表结构,依靠的是记录头的next_record字段。

记录删除不是物理删除,否则挪动其它记录代价很大,因此在记录头上有个delete_mask。比较自然的做法是删除的记录会从有效记录的链表中拿掉,被删除的记录也组成一个垃圾链表,新记录插入的时候可以重用。

每条记录在本页中会有一个逻辑位置,是记录头中的heap_no。

数据记录的大致状况如下图















6.Page Directory用来加速页内记录查找。具体做法是把记录按相邻关系分成很多组,每组最后一条数据头部n_owned属性记录该组记录数,并把每组最后一条数据的地址偏移量记录到页目录。查找的时候通过页目录二分查找到记录对应的组,然后再组内顺序查找。

页内部的记录会严格主键自增么?

应该不会,否则不顺序插入时移动的代价太高,应该只有链表上的逻辑顺序。但页面之间的顺序应该会保持。

数据记录行

有多种格式,看一下compact格式的












1.变长字段长度列表描述对应变长列的长度,按列的逆序放置,只存非null列的内容。

2.为了节省空间对null值做特殊处理,null值列表按位图的方式存放。

3.每行数据的最大长度是有限制的,而每个页的大小限制是16k,如果有超大字段导致溢出,会溢出到其他的页,数据行会存一部分数据和一个指向其他地址的指针




















关注的第二个问题,记录存储和b+ tree的关系?

B+ Tree索引

在不考虑索引的情况下页和数据记录已经组织成链表结构












加入和数据页类似的目录项页组织成b+ tree之后就变成下面这样,




















目录项和数据记录以比较相似的方式组织称目录项页,主要的区别是record_type不同,再者就是没有数据记录里面那么多列。

使用主键进行排序,叶子节点直接存储所有数据列的就是聚簇索引。

用其他列C2进行排序,叶子节点只存储C2+PK两个列的值的b+ tree是二级索引,二级索引查询要多一次回表操作。

存储碎片问题

删除空间重用的过程

1.每当新插入记录时,首先判断PAGE_FREE指向的头节点代表的已删除记录占用的存储空间是否足够容纳这条新插入的记录,如果不可以容纳,就直接向页面中申请新的空间来存储这条记录

2.如果可以容纳,那么直接重用这条已删除记录的存储空间,并且把PAGE_FREE指向垃圾链表中的下一条已删除记。个人理解这一步会造成记录逻辑顺序和物理顺序不同。

3.如果新插入的那条记录占用的存储空间大小小于垃圾链表的头节点占用的存储空间大小,那就意味头节点对应的记录占用的存储空间里有一部分空间用不到,这部分空间就被称之为碎片空间

4.当页面快满时,如果再插入一条记录,此时页面中并不能分配一条完整记录的空间,这时候会首先看一看PAGE_GARBAGE的空间和剩余可利用的空间加起来是不是可以容纳下这条记录,如果可以的话,InnoDB会尝试重新组织页内的记录,重新组织的过程就是先开辟一个临时页面,把页面内的记录依次插入一遍,因为依次插入时并不会产生碎片,之后再把临时页面的内容复制到本页面,这样就可以把那些碎片空间都解放出来(很显然重新组织页面内的记录比较耗费性能)

所以碎片产生原因是删除数据就会导致页(page)中出现空白空间,大量随机的DELETE操作,必然会在数据文件中造成不连续的空白空间。而当插入数据时,这些空白空间则会被利用起来.于是造成了数据的存储位置不连续。物理存储顺序与逻辑上的排序顺序不同,这种就是数据碎片。update操作除了原地的之外,也有可能产生这种问题。

不是说数据记录先存储在内存中的么?

内存存储

所有读写操作都走磁盘io并不经济,所以mysql会有缓存叫做Buffer Pool。










1.如上图,Buffer Pool是一块连续的内存空间用来存储数据页,这些数据页和表空间(文件系统)的数据页应该是一样的。

2.控制块描述对应页的控制信息包括该页所属的表空间编号、页号、缓存页在Buffer Pool中的地址、链表节点信息、一些锁信息以及LSN信息

3.我们需要知道哪些页面是空闲的,哪些页面是脏的需要flush,所以就有了两个链表,这两个链表都是通过控制块存的指针来组成

4.读数据页的时候会先从Buffer Pool里面找,需要一个hash map来快速查找,key是表空间号 + 页号(这也是inno db定位页的统一坐标),value是缓存页地址

5.Buffer Pool空间有限,所以需要用lru来管理,简单的lru碰到预读和范围扫描这些范围读取的场景都会相当于无效,所以可以对lru分区成old和young,对于范围扫描先加载到old,对于old区访问小于一定时间间隔才到young。对于young区的热数据也不需要每次访问都移动,进一步分区只有较不频繁的分区被访问才移动。

6.可以使用多个Buffer Pool提高多线程性能。

应该有个write ahead log吧?

redo log

redo log就是inno db中的write ahead log,把事务提交是的随机io变成redo log的顺序io+异步刷盘时的批量io。redo log的特点是顺序写,占用空间小主要记录存储表空间ID、页号、偏移量以及需要更新的值。

之前比较naive的想法是记录个sql就行了,但实际上会比较复杂,redo log更像一个前后的状态变更,比如插入一条数据可能会更新多个索引,对于每个索引有可能造成b tree分裂这种情况会更新多个页面。如果纯按物理状态变更的方式来记日志可能会记相当多的信息,比如File Header、Page Header、Page Directory等等部分,所以感觉inno db采用的是物理+逻辑得折中方案,比如下面这个MLOG_COMP_REC_INSERT类型的redo log
















向某个索引对应的B+树中插入一条记录的这个过程必须是原子的但又可能涉及到多个页的修改产生多条redo log,这些日志被编成一个组称作一个Mini-Transaction。

redo log也被组织成页的形式,不同的是页的大小是512字节,写入的时候也是先写内存在合适的时机刷盘,在内存的时候也是连续的内存空间被组织成log buffer。并发事务的redo log是可能交替写入的,写入过程可以看下图。








有一个较为重要的属性叫Log Sequence Number(LSN),代表系统写入的redo日志量的总和,也是当前写入日志的逻辑时间。

undo log

之前一直有疑问为什么需要undo log,如果只是为了回滚事务状态,为啥不能直接用redo log反向操作?现在我理解主要原因是(1)事务能并发,用结构单一的redo log回溯可能复杂度较高,undo log有事务维度的数据结构比较好处理(2)更重要的是需要支持mvcc,所以需要不同的数据结构

数据记录维度

数据记录有几个和undo log相关的字段








1.trx_id,事务id,注意数据记录只有一个事务id字段,意味着唯一占用,对数据记录的操作应该是整个事务内加锁的。之前猜测mysql mvcc遇到写写并发然后类似于乐观锁的方式让一个事务失败是错误的。

2.roll_pointer,数据记录指向undo log的指针。

insert,update,delete在undo log上的表现很不相同,所以要分开看

insert日志结构

insert操作对应的undo操作是删除就好,而删除也只是状态位和链表处理,即使insert过程中产生了页分裂,也不需要把之前的页合并回去。











delete日志结构

delete操作分两个阶段,第一阶段只更新状态位在事务提交阶段才会更新delete链表,如果要回滚只需要考虑第一阶段的影响。













old trx_id,old roll_pointer,关联之前的undo log形成一个链表,方便后面回溯。

update日志结构

update操作分更新主键和不更新主键的情况,不更新主键又根据被更新列的存储空间是否发生变化而不同。(1)如果更新列存储空间不变就可以做就地更新 (2)如果列的大小发生改变就需要先删除(状态位+链表),再插入 (3)更新主键也是先删除再插入,但插入位置可能不是当前页了

不更新主键的日志结构如下,和delete的undo log类似














更新主键的日志会是两条,TRX_UNDO_DEL_MARK_REC和TRX_UNDO_INSERT_REC,之所以会这样是因为相当于产生了两条记录,两条记录的状态都需要跟踪

相关逻辑结构











1.从整个结构看在系统表空间的第5号页面中存储了128个Rollback Segment Header页面地址,每个Rollback Segment Header就相当于一个回滚段。这是因为可能并发事务多,一个回滚段描述不了所有事务。

2.每一个Rollback Segment Header页面都对应着一个段,这个段就称为Rollback Segment,翻译过来就是回滚段。回滚段管理所有Undo页面链表的头节点。

3.undo log分为两个大类,TRX_UNDO_INSERT和TRX_UNDO_UPDATE,两种日志不能混着放。每个事务可能有4个undo log页面链表,除了log类型还有普通表和临时表维度。区分临时表的原因是因为mysql会为undo log本身也记录redo log,但临时表不需要持久化所以不需要记redo log,所以做了这种区分。

为事务分配Undo页面链表详细过程

1.到系统表空间的第5号页面中分配一个回滚段,其实就是获取一个Rollback Segment Header页面的地址

2.看一下这个回滚段的两个cached链表有没有已经缓存了的undo slot

3.如果没有缓存的undo slot可供分配,那么就要到Rollback Segment Header页面中找一个可用的undo slot分配给当前事务

4.找到可用的undo slot后,如果该undo slot是从cached链表中获取的,那么它对应的Undo Log Segment已经分配了,否则的话需要重新分配一个Undo Log Segment,然后从该Undo Log Segment中申请一个页面作为Undo页面链表的first undo page

5.然后事务就可以把undo日志写入到上边申请的Undo页面链表了

MVCC

事务这块有个不完备的总结就是基本都是靠版本号来做可见性控制。我们从一个观察者事务的角度来看mvcc。观察者事务有一个ReaderView的概念,在一个ReaderView里面包含 (1)m_ids 生成reader view时所有活跃的读写事务列表 (2)min_trx_id m_ids中的最小值 (3)max_trx_id 表示生成ReadView时系统中应该分配给下一个事务的id值。(4)creator_trx_id 表示生成该ReadView的事务的事务id,也就是当前观察者的事务id

比如观察者看到的版本链是这样的,









读取记录的时候的过程大约是,

1.顺着版本链由新到旧的方向逐个比较trx_id

2.如果trx_id和观察者事务相同,意味着当前事务做的修改当然可见。

3.如果trx_id< min_trx_id,说明这个修改版本早在当前reader view创建前就提交了所以可见,算是个读已提交的行为。

4.如果trx_id>= max_trx_id,说明修改版本产生在reader view生成之后,这种情况不可见。

5.如果min_trx_id<=trx_id<max_trx_id,这种情况需要比较trx_id和m_ids,如果trx_id在m_ids中,说明创建ReadView时生成该版本的事务还是活跃的,该版本不可以被访问。

6.通过调整创建reader view的策略来达成read commit或者repeatable read隔离级别。read commit在每次读的时候创建reader view而repeatable read仅仅在观察者事务开始的时候创建reader view。

7.再强调一次防止写写冲突是通过事务时间内对记录加锁实现的。

Insert Buffer

1.大量insert的时候主键可能是顺序insert的,但是二级索引并不一定,这样会产生大量随机io。

2.如果二级索引非唯一索引就可以引入insert buffer先缓冲一批二级索引的写入然后在某个时间批量刷盘。

3.不能是唯一索引的原因是唯一索引判断重复需要走二级索引,大量非顺序插入时同样会产生随机io,做insert buffer失去了优化的意义。

4.如果宕机没有同步到二级索引的insert buffer里面的数据恢复需要不少时间。

表连接原理

简单理解表连接就是一个多重for循环
  
for each row in t1 {   #此处表示遍历满足对t1单表查询结果集中的每一条记录
    
    for each row in t2 {   #此处表示对于某条t1表的记录来说,遍历满足对t2单表查询结果集中的每一条记录
    
        for each row in t3 {   #此处表示对于某条t1和t2表的记录组合来说,对t3表进行单表查询
            if row satisfies join conditions, send to client
        }
    }
}

代入到实际点的场景就是对驱动表t1的每条记录去t2表查询符合条件的记录,这样每次访问t2表都会把t2表的数据从磁盘加载到内存,代价相当大。

Block Nested-Loop Join,引入了join buffer,join buffer就是执行连接查询前申请的一块固定大小的内存,先把若干条驱动表结果集中的记录装在这个join buffer中,然后开始扫描被驱动表,每一条被驱动表的记录一次性和join buffer中的多条驱动表记录做匹配,因为匹配的过程都是在内存中完成的,所以这样可以显著减少被驱动表的I/O代价。

总觉得查询计划还是挺神奇的,怎么运作的呢?

查询优化

信息收集

1.统计表的行数,按照一定算法(并不是纯粹随机的)选取几个叶子节点页面,计算每个页面中主键值记录数量,然后计算平均一个页面中主键值的记录数量乘以全部叶子节点的数量就算是该表的n_rows值

2.聚簇索引占用页面数和其它索引占用的页面数,从数据字典里(SYS_INDEXES)找到表的各个索引对应的根页面位置,找到叶子节点和非叶子节点对应的几个链表的头,然后统计对应的区的数量和零散页面的数量。简单说就是可以从数据结构的概要信息中拿到。

子查询优化

1.物化,子查询直观的逻辑是直接执行子查询然后放内存里面,但是有可能遇到内存放不下的情况所以引入了临时表,会根据数据集大小选择内存存储或者磁盘存储,这个过程也可以叫物化。

2.子查询转连接,操作方法可能有子查询的表直接上提进行连接,建立临时表去重再进行连接,对于有大量重复记录的进行松散扫描等等。


运行态

后台线程

1.Master Thread - 核心的后台线程,主要负责将缓冲池中的数据异步刷新到磁盘,保证数据的一致性,包括脏页的刷新、合并插入缓冲(INSERT BUFFER)、UNDO页的回收等

2.IO Thread - InnoDB 1.0版本之前共有4个IOThread,分别是write、read、insert buffer和log IO thread。

3.Purge Thread - 事务被提交后,其所使用的undolog可能不再需要,因此需要PurgeThread来回收已经使用并分配的undo页。

4.Page Cleaner Thread - 是在InnoDB1.2.x版本中引入的。其作用是将之前版本中脏页的刷新操作都放入到单独的线程中来完成。而其目的是为了减轻原MasterThread的工作及对于用户查询线程的阻塞,进一步提高InnoDB存储引擎的性能。

Master Thread

1.0.x版本之前的master thread的主要逻辑如下,后续版本做了优化,主要是之前写死的地方做了灵活优化,把刷脏页的操作分离到其它线程

1.整体逻辑有两个循环,约1秒一次的的循环和10秒一次的循环

2.每秒一次的操作大致有,undo log刷盘,合并insert buffer,刷盘buffer pool 100个脏页,如果没有没用活动会切换到background loop

3.每10秒的操作大致有,刷盘100个脏页,合并至多5个insert buffer,undo log刷盘,删除无用的undo log页,刷盘100个或者10个脏页

4.background loop,如果没有用户活动(数据库空闲时),删除20个无用的undo页,合并20个insert buffer,不断刷新100个页

Binlog相关

3阶段提交

1.事务提交过程中涉及到redo log,binlog,以及事务状态等多个资源协调,所以很自然的是多阶段提交的过程,但是这个和分布式事务的3pc还是有区别的。

2.简单理解就是1阶段写redo log,2阶段写binlog而且如果2阶段成功一定会进行第3阶段,3阶段写事务状态。


Group Commit

1.目的很简单为了提升io性能,对redo log,binlog刷盘做批量io优化。但同时带来的另外一个优化是在slave端可以做并发复制。

2.每个group内的事务是可以并行的是因为mysql把一个时间点内就绪的事务分成一个group,就绪的事务必然没有资源依赖了,所以也可以判断group内的事务没有互相依赖。依赖判断主要还是基于timestamp来做的,也叫做logical lock。

3.mysql 8.0引入write set机制来判断事务间的依赖,感觉是在判断事务读写记录有没有交集,提供比logical lock更好的并发性。参考Fastest Parallel replication method in MySQL 8

4.可以参考文章 MySQL组提交 并行复制原理

Binlog Server

1.可以参考kingbus里面的文档

2.binlog server个人理解主要场景还是在mysql replication体系提供binlog复制

3.本质上说binlog server是一个没有存储引擎的mysql,也类似于mysql配上black hole引擎

4.binlog server延迟比实际mysql小,所以在多级mysql同步体系里面可以解决大延迟的问题

5.binlog server在facebook可以搭配hdfs存储引擎,解决binlog存储时间短占空间的问题

6.binlog server还可以替代从库,因为同步快。然后新主从binlog server追上数据就可以工作

并发优化

  1. 参考https://zhuanlan.zhihu.com/p/151397269 以及后面的系列
  2. mysql5.6的问题是对b tree有结构修改,比如update时候分裂,会有整个index级别的X排他锁,阻塞所有读操作,并发度底
  3. mysql8.0引入index级别的sx意向锁不阻塞读,update分裂的时候加index sx锁,并且只在分裂节点和它的parent node加x排他锁。这样不阻塞读,但是单个index多个update分裂无法并发
  4. 8.0需要index sx锁是因为b tree搜索路径自顶向下而加锁路径自底向上容易死锁。polar db的优化是去掉index sx锁,b tree node上加一个指向分裂产生的新节点的指针把分裂过程做成两阶段,每阶段只加锁一个节点,中间状态合法(父节点查不到再用分裂指针查一次)。这样就做到了多个smo的并发。
  5. 下一个问题是多个并发读都会访问根节点并加S锁,在多核架构下多核S锁会互相invalidate cache line会造成10%-20%的性能损失。这个问题学术界有一些解法,但都不是很完美。









2021年4月4日星期日

学习范畴论的一些总结

 动机


1.以抽象的方法处理数学概念,将这些概念形式化成一组组的“物件”及“态射”。数学中许多重要的领域可以形式化为范畴。使用范畴论可以令这些领域中许多难理解、难捉摸的数学结论更容易叙述证明

2.研究范畴就是试图以“公理化”的方法抓住在各种相关连的“数学结构”中的共同特性,并以结构间的“结构保持函数”将这些结构相关起来

3.以群为例,其态射为群同态。两个群间的群同态会严格地“保持群的结构”,这是个以将一个群中有关结构的讯息运到另一个群的方法,使这个群可以看做是另一个群的“过程”。因此,对群同态的研究提供了一个得以研究群的普遍特性及群公理的推论的工具

4.范畴论研究结构,结构有点核心基石的感觉,比如如果没有数字2质数体系就不存在,因为无法满足每个数的质数乘积表示是唯一的。比如(0,1)加法,(-1,1)乘法,(0,180)旋转,本质是相同的。在范畴论里面会用箭头来表示这个结构

范畴是什么


1.范畴可以理解成集合加上额外的元数据,这些额外元数据描述两个对象相互关联的所有方式,包括描述两个对象等价的所有方式

2.对一个对象的认识,可以是看它的组成(细分再细分:分子,原子,原子核,等等 [公式] ),这是集合论的思想,但是也可以是看它与其他对象的关系,这是范畴论的思想

3.所有的集合组成一个范畴,所有的线性空间组成一个范畴,所有的群组成一个范畴,所有的流形也组成一个范畴,因此范畴是集合、线性空间、群、流形的抽象。互联网可以看做一个范畴,facebook也可以看做一个范畴。

4.范畴最容易理解的一个例子为集合范畴,其物件为集合,态射为集合间的函数。但需注意,范畴的物件不一定要是集合,态射也不一定要是函数

5.一个数学概念若可以找到一种方法,以符合物件及态射的定义,则可形成一个有效的范畴,且所有在范畴论中导出的结论都可应用在这个数学概念之上

基本概念


1.范畴(Category),范畴包含实体对象,实体对象间的映射,映射能够复合并且符合结合律,存在单位映射而且单位映射复合之后保持之前的映射不变

2.函子(Functor),再抽象化一次,范畴自身亦为数学结构的一种,因此可以寻找在某一意义下会保持其结构的“过程”;此一过程即称之为函子。函子将一个范畴的每个物件和另一个范畴的物件相关连起来,并将第一个范畴的每个态射和第二个范畴的态射相关连起来。实际上,即是定义了一个“范畴和函子”的范畴,其元件为范畴,(范畴间的)态射为函子。

3.自然变换(natural transformation),将一个函子映射至另一函子的方法,再抽象化一次基于函子范畴。函子范畴,两个范畴之间的所有函子形成的范畴,态射是函子间的自然变换。

4.群,一个集合以及定义在这个集合上的二元运算,满足群的四条公理,封闭性、结合性、单位元、反元素

5.幺半群(Monoid),只有单位元和二元运算,没有反元素的群。可以看成只有一个元素的范畴,任何箭头都是可复合的,这些箭头不一定是恒等,比如对于整数集合(一个元素)+1映射,所有这样的映射(箭头)组成的集合相当于一个能乘但不一定能除的集合像自然数,所以有一个只有一个元素的范畴就是一个幺半群。

6.同构(isomorphism),指的是一个保持结构的双射。在更一般的范畴论语言中,同构指的是一个态射,且存在另一个态射,使得两者的复合是一个恒等态射。可以简单的认为是范畴论体系下面的=

7.等价范畴,对其中一个范畴成立的定理,可以既定地转换成另一个范畴的定理。用来描述这种情形的主要方法是“范畴的等价性”,由函子给出

8.泛性质,小明和他的父亲大明之间存在态射“小明的父亲是大明”。而这个态射又可以分解为态射“小明的母亲是大红”和态射“大红的丈夫是大明”的组合 。而如果存在这样一种态射,范畴内的所有态射都可以分解为该态射和另一种态射的组合。则称该态射在该范畴内是一种“具有泛性质的态射”,简称“泛态射”。所有“性质”所拥有的性质就是“泛性质”

9.hask范畴,对象是haskell里面的所有类型,态射是haskell里面所有的函数。因为haskell里面的所有的函数理论上都可以是non-terminating的,所以所有的haskell type都可以被认为是lifted过的,所以才有一个新的category来描述
 
10.伴随函子,一个范畴C可以通过函子G到D,再通过函子F回到 C,那么F和G就是伴随函子

11.同态(homomorphism),不是双射只是单射,比如x=x+2是同构,x=x^2是同态

12.hom-set,一个范畴中两个object A B间所有的态射的集合

13.hom-functor,把object a 映射成 a->x的集合的functor

14.natural isomorphism 自然变换而且两边同构,所以也是可逆的自然变换。

15.representable functor,和hom-functor自然同构的都是reprentable a和f a -> x 两个范畴之间存在的functor叫做Representable,这个functor可以看做一种带key的记忆,通过key来记录f运行后的值,所以Representable有两个操作tabulate和index

16.adjunction 同构太强要求太高,一个偏弱点的结构是adjunction,两个范畴C,D,两个functorL,R 如果RL是d->d',然后通过另一个映射unit能d->d',L到c'另一个映射counit c'-c,然后R到d 这样的弱一些的关联叫adjunction,另一个等价的说法是 𝐂(𝐿𝑑, 𝑐)  𝐃(𝑑, 𝑅𝑐) 同构,这两个都是hom-set

重要结构的理解


Initial/Terminal Object

1.初始对象S是对于范畴内所有其它对象X有且仅有一个态射f:S->X。比如偏序集合范畴里面最小的元素(有的偏序集合没有Initial比如整数),比如普通集合和函数的范畴里面的empty set(haskell里面Void)








2.终点对象T是范畴内所有其它对象X有且仅有一个态射f:X->T。比如偏序集合里面的最大元素,比如普通集合范畴里面的singleton(haskell里面的(),函数是unit)








3.对偶性,对于原来的范畴定义一个对偶范畴,里面所有箭头反向,那么新范畴里面的初始和终点对象也会对换。箭头反向是范畴论研究常用的套路。

Pushouts/Pullbacks


1.两个态射f:A->B和g:A->C,它们的pushout是对象D,有两个态射d1:B->D和d2:C->D。D是所有满足上面条件的对象组成的子范畴中的初始对象













2.pullback就是把上面的关系反向















3.pushout/pullback描述的结构的一个重要特点是两个态射共享定义域(domain)或者值域(codomain)

Products/Coproducts


1.Products是指对于对象Ai 有一个对象P以及一组态射gi:P->Ai,其中P是满足条件的对象组成的子范畴中的终点对象。这里终点对象的意义在于可以把P'->Ai分解成P->Ai和P'->P的复合









2.Coproducts是指对于对象Ai 有一个对象P以及一组态射gi:Ai->P,其中P是满足条件的对象组成的子范畴中的起点对象。coproducts可以类比成加法。








3.在haskell中products是一个tuple (a,b)和两个函数fst,snd,coproducts是data Either a b = Left a | Right b

Limits/Colimits


1.对于任意一个转换图有对象Ai和态射ai,Limit是指对象L以及一些列态射li,li:L->Ai和lj:L->Aj,ax:Ai->Aj,ax.li=lj L是所有满足上面条件的对象组成的子范畴中的终点对象。








2.Colimits就是把上面的图像反过来









3.终点对象,pullbacks,products是limits的特例,初始对象,pushouts,coproducts是colimits的特例

Free Monoids


比如free monoid里面的list,对于[2],[3]只是append成[2,3]而不是[6],这种结构只是简单的累积参数而不是把信息隐含在映射中,有点lazy evaluation的意思。

在free forgetful adjunction结构中左边范畴的映射少因为要保持更多的结构,右边的映射多,但是两边的hom-set要同构,这说明对于往左的Functor F,必须包含必须的结构无关的对象,结构无关的对象叫做free object,个人理解[2,3]这种是结构无关,[6]这种是结构有关


Monad


1.首先是Monad是自函子范畴上的一个幺半群,自函子范畴是因为Monad要做函数复合,如果in和out的范畴不同就没法玩了。幺半群是因为Monad的动机是要做不断的复合同时保持结构,能想象到的类似的结构就是幺半群,按幺半群的定义乘法(tensor product)是复合,单位元是id functor,天然满足结合律。也可以这样理解,不是所有的endofunctor都是Monad,而是定义了复合而且满足幺半群条件的自函子才是Monad

2.上面的说法容易有的一个理解的误区是自函子作用的范畴,容易理解成a->M a 所以就成了不同的范畴,但实际上a和M a可以在一个更大的范畴中,就像hask范畴包含所有的基础类型以及之上的复合类型

3.从功效角度看想做连续的函数复合,只要f的返回类型和g的参数类型一致就行了,但这样要求太严格,而且无法传递函数外的信息,所以需要一个通用结构来传递函数外的信息,简单看就是在返回值上面包一层,这就成了Monad

4.还有一个Kleisli维度的说明,但Kleisli范畴本来就是定义在Monad之上的范畴,object是一般范畴的object本身,而映射是a->M[b]这种,这样的范畴就是Kleisli范畴

Yoneda Lemma


1.描述上是说C(a,x)到F(x)之间的自然变换和F(a)有一一对应的关系

2.可以分两步看这个关系,首先固定x到a变成C(a,a),这个时候任取C(a,a)的一个点p'会对应一个函数g,这个函数g又通过functor F一传导就变成了Fg,把F里面的点q(对应id),变成了q'所以p确定q就确定就是个固定的函数然后放开x,类似的𝑞′ = (𝐹𝑔)𝑞,只要选了g就能确定q。 

3.这个里面的魔法是p能通过functor和id函数进行传导绑定到q,本来f和C里面的元素都可以随意变化,但在hom-functor里面进行了强行锁定,绑定后真正在变化的只有g,而信息的核心就是a,C(a,a)里面的点p,F(a)里面的点q

4.米田引理的意义是hom-functor的信息是最完整的,通过对hom-functor做自然变换得到的functor可能会损失信息

5.在haskell里面有 forall x . (a -> x) -> F x ≅ F a ,米田引理说明这两种表示,信息量相同。把F换成id,就得到了continuation的表示

6.把C(a,-),C(b,-)看成元素得到的category,这个过程叫Embedding,C->[C,Set],这个过程是完全保持结构的,这个过程的价值在于可以通过对Set的了解去反过来研究C(感受不到...)

F-Algebras


1.把一个代数体系中的基本运算用| encoding在一起就是一个F-algebra比如 type Algebra f a = f a -> a比如 data RingF a = RZero | ROne | RAdd a a | RMul a a | RNeg a 

2.不动点Fix f=f (Fix f) 因为代数系统通常是能递归的,看到Fix可以理解成把f多应用一次

3.F-Algebras范畴,object是a和F组成的代数系统,(a,f)->(b,g)是映射,假设原生范畴有m:a->b 那F m:: F a -> F b

4.Catamorphisms,这个东西描述一个递归的代数系统和一个普通代数系统的关系,定义cata alg = alg . fmap (cata alg) . unFix  cata传入一个普通代数系统,返回一个递归代数系统到具体值类型a的函数

5.Coalgebras 把F-Algebras的箭头反向,a->F a  定义ana coalg = Fix . fmap (ana coalg) . coalg 经典的例子是data Stream e = Stream e (Stream e) 一个例子是把stream映射到primes

6.foldr本质上说是特殊化版本的cata,也可以看到cata有多抽象,同时可以学到一个经典的patter,通常用commute图分解一个态射,看起来是走了一圈,其实是分解了,感觉用functor lift一下然后再回去也是这种技巧


Lawvere Theories














1.再次领教范畴论终极大招,为了研究一个复杂的范畴投影到一个简单的范畴

2.Lawvere理论是为了抽象所有的代数运算体系(algebra),代数体系都是先选定一个定义域比如整数,实数,复数,然后代数运算都是n个参数运算出一个结果在范畴论的语言里面可以表达为
alpha::a^n->a

3.Lawvere理论的做法是把代数体系表达成一个L范畴,L范畴可以被映射到一个更简单的基于集合的范畴FinSet,集合范畴的object就是0个元素的集合,1个元素的集合,2个元素的集合。。。但直接这样映射有些关系对应不上所以先选择一个同构的集合F去掉n个元素集合的多种表达方式,在用F的逆范畴IF把*转换成+,这样就完成了映射,可以在IF里面研究L了

4.L范畴里面的关键信息是那些定义n-ary操作的态射,所以的L组成一个范畴Law,Law里面的态射举个例子可以是从加法群映射到乘法幺半群



2021年1月21日星期四

jvm源码笔记

 多年前立下的flag终于算是还了愿。

调试环境

参考编译openjdk8,已经讲得很详细了。

调试参数

-Xcomp 强制编译

-XX:+PrintInterpreter 查看解释器汇编,要先sudo apt-get install libhsdis0-fcml 
sudo cp /usr/lib/jvm/java-8-openjdk-amd64/jre/lib/amd64/hsdis-amd64.so /usr/lib/jvm/java-8-oracle/jre/lib/amd64/hsdis-amd64.so

-XX:SuppressErrorAt=/resourceArea.hpp:63 避免调试过程中的一些错误

-XX:+UnlockDiagnosticVMOptions -XX:+PrintAssembly -Xcomp 打印出编译的代码
-XX:+PrintCompilation 查看编译日志 
-XX:+PrintStubCode 查看桩代码
-XX:CompileCommand=print,*MyClass.myMethod 只打印一个方法的汇编代码

-XX:+PrintIdeal:输出Ideal日志
-XX:PrintIdealGraphFile=ideal.xml:将理想图存储到ideal.xml文件
-XX:+PrintIdealGraphLevel=4 输出理想图构造的详细过程


启动过程

整体流程中的重要过程


入口 -- bin/main.c

装载动态链接库 -- LoadJavaVM(java_md_solinux.c)

初始化启动虚拟机 -- InitializeJVM(java.c)

执行main方法 -- LoadMainClass(java.c)

启动过程中的线程1是main方法线程本身,线程2是创建jvm的线程,再往后就是gc等工作线程了。

启动虚拟机流程中的重要过程


设置各种系统参数比如pagesize,cpu核数 -- (os::init)

继续操作系统相关初始化,比如信号处理,启动线程栈底计算 -- (os::init_2)

各种管理相关的计数器初始化 -- (management_init)

初始化字节码查表 -- (bytecodes_init)

初始化code cache主要是申请内存和生成cpu cache flush例程 -- (codeCache_init)

在code cache中生成一些基础例程比如异常处理,原子变量操作,例程会在字节码解释或者jit生成代码中被调用 -- (stubRoutines_init1)

初始化堆,metaspace(包括gc策略)等等 -- (universe_init)

初始化解释器,最重要的是初始化template table -- (interpreter_init)

生成一些重要的例程比如resolve_virtual_call_C,uncommon_trap_blob -- (SharedRuntime::generate_stubs)

genesis,初始化系统字典和一些核心类型 -- (universe2_init)

生成一些重要基础类实例,比如各种异常类 -- (universe_post_init)

生成另一批基础例程比如数组拷贝,数学运算等 -- (stubRoutines_init2)

参考文章


方法调用相关

java方法调用有多种场景,jvm直接调用,字节码解释执行调用,jit编译后的调用。

jvm直接调用


入口 -- 几种调用方式都会通过JavaCalls::call

建立java栈帧 -- 通过c调用java需要一个适配的例程,_call_stub_entry指向这个例程,
这个例程通过generate_call_stub(stubGenerator_x86_64.cpp)生成。generate_call_stub进行java方法调用的时候会调到一个entry_point去执行。

解释器例程 -- 进入解释器调用目标方法同样通过一个例程(entry_point)实现,entry_point的例程是通过generate_normal_entry(templateInterpreter_x86_64.cpp)方法生成。generate_normal_entry会创建解释器栈,把目标方法地址设置到r13,执行目标方法。


通过字节码调用

invokespecial,invokevirtual等字节码通过解释器调用方法的过程稍有不同。

1.rewrite -- javap看到的类似invokespecial #8是指向常量池的,常量池的数据结构比较紧凑 ,需要多项来描述方法调用在内存中使用不方便,所以要转换成ConstantPoolCache(cpCache.hpp) 同时invokespecial #8里面的index也要通过rewrite指向ConstantPoolCache里面对应的位置。过程发生在link_class(instanceKlass.cpp),可以debug rewrite_member_reference(rewriter.cpp)。当然rewrite还可以做其他类型的优化。

2.设置方法解释器入口 -- Method::link_method

3.TemplateTable::invokespecial -- invokespecial指令对应的汇编代码通过TemplateTable::invokespecial生成。该过程首先通过index访问ConstantPoolCache拿到要调用的方法的methodoop(prepare_invoke),然后跳转到方法的解释器入口interpreter_entry(jump_from_interpreted),这个入口是generate_normal_entry生成。

4.generate_normal_entry -- 最重要的就是建立解释器栈祯(generate_fixed_frame),过程中会设置目标方法的地址lea(r13, Address(r13, ConstMethod::codes_offset() 


编译后的方法入口

1.编译好的代码包装在nmethod(nmethod.hpp)里,里面有两个入口UEP和VEP,VEP是真正的入口而UEP主要用在monomorphic inline cache。nmethod又被包装在java方法元数据对象Method(method.hpp)里面。

2.Method有几个字段,
_i2i_entry _adapter _from_compiled_entry _from_interpreted_entry
对应着jvm解释模式和编译模式的adapter行为,这个adapter为了适配calling convention。

_i2i_entry 一直指向解释器入口
_from_interpreted_entry 在_i2i_entry和i2c adapter stub之间切换
_from_compiled_entry 在c2i stub和VEP之间切换
_adapter 指向i2c2i adapter stub,通过它可以拿到i2c或者c2i adapter stub

3.上面这些字段在link_method(method.hpp)的时候会进行初始设置。


虚函数调用相关

首先看vtable

1.vtable的位置在instanceKlass对象实例内存位置的后面(klassVtable::table())

2.vtable初始化过程中会先拷贝父类的vtable然后update其中重写的方法然后设置当前类的方法。代码路径可看
klassVtable::initialize_from_super->update_inherited_vtable->put_method_at
如果一个 Java 方法可以被继承和重写,则最终通过 put_method_at函数将方法地址替换,完成 Java 方法的动态绑定

inline cache

1.没有cache的情况下动态绑定的语言方法调用的时候可能要顺着继承链查找方法损耗性能。一种非inline的cache--first-level method lookup cache的做法是一个全局的map缓存,java因为继承的时候拷贝了父类的vtable也类似于实现了。参考inline caching

2.基于一个调用点(call site)对应的多态对象的类型多数情况下是不变的这个假定,直接把目标方法的地址内联到调用点,在调用的时候做一个类型判断如果类型不匹配就退回到查找。这种方式的性能提升在于用一次类型比较替换了map查找,可以用上分支预测。

3.为了应对调用点在两个或者有限几个类型间反复跳的状况有了inline cache的级别,Monomorphic(单类型)->Polymorphic(少数几个类型)->Megamorphic(无限定)

4.jvm实现可以看CompiledIC::compute_monomorphic_entry(compiledIC.cpp)

class hierarchy analysis

JIT对于多态调用有可能做优化

1.首先在类结构体系里面找method,如果是唯一的实现ok了,参考find_monomorphic_target

2.否则通过变量actual_receiver_is_exact来判断,计算自type lattice信息,如果true,直接resolve_invoke出method。

反射调用为什么慢


1.反射首先是查询method对象慢,但一般都会被缓存

2.反射的实现分native和字节码动态生成两种,native由于不被jvm管理完全无法做内联较慢但加载快,热点方法走动态生成走MethodAccessorGenerator,生成一个强类型的实现,
  生成的代码可以被内联。但是method.invoke方法本身可能后面会对应多个GeneratedMethodAccessor所以很难同时记录所有调用点,所以可能发生没有被内联的情况。

3.MethodHanle能被优化MethodHandle.invoke()的形式参数与返回值类型都是准确的,所以只需要在链接方法的时候才需要检查类型的匹配性,而不必在每次调用时都检查。
  而且MethodHandle是不可变值,在创建后其内部状态就不会再改变了;JVM可以利用这个知识而放心的对它做激进优化,例如将实际的调用目标内联到做反射调用的一侧

4.方法参数的包装转换,方法权限的检查也会有一些性能消耗


invoke dynamic相关

1.invokedynamic有两个相关的概念,CallSite和MethodHandle,CallSite是调用点,MethodHandle是方法句柄也可以理解成对方法的链接。invokedynamic参数需要一个bootstrap method来查找CallSite和MethodHandle

2.invokedynamic不像其他几个invoke指令那样要求实现接口或者对应的类型上有对应的方法,invokedynamic相当于把方法链接这个过程抽象出来让程序员来实现。

3.其实reflection也可以看成链接不过一个是无法完全内联导致的性能问题,第二个是链接只能通过名字查找比较死。而MethodHandle在链接过程中可以curry,可以各种combine,可以实现method_missing等能够比较灵活的实现动态语言的需求。


lambda的实现方式


1.比较naive的方法是用生成匿名内部类的方法实现,这种实现方式会导致大量的io读取性能差

2.在声明lambda的类里面会生成static方法对应lambda的逻辑,如果有捕获变量也加到static方法的参数列表中

3.调用lambda方法的时候先用invokedynamic生成MethodHandle去调用InnerClassLambdaMetafactory生成一个实现了lambda对应方法的class,然后用invokeinterface之类的方式去调用实际方法的实现(通过代理)

4.方法调用会被内联优化到和直接调用接近,参考jvm是怎么实现invokedynamic的


解释执行字节码的过程

1.hotspot默认使用的是模板解释器,templateInterpreterGenerator(解释器生成器) + templateTable(字节码对应的机器码实现) + templateInterpreter(解释器)

2.给字节码生成对应的汇编例程TemplateTable::initialize() TemplateInterpreterGenerator::generate_all()

3.字节码和例程建立关联TemplateInterpreterGenerator.set_entry_points_for_all_bytes

4.字节码加载进入内存发生在类加载ClassLoader::load_classfile->ConstMethod::set_code

5.执行过程,拿istore做例子,对应的汇编生成在TemplateTable::istore() 实际汇编如下
  0x00007f9869034e60: mov     (%rsp),%eax
  #栈顶缓存技术,把栈顶元素(方法调用用这种手法很常见但这里是指令级别)放到寄存器里面提升性能
  #参考http://book.51cto.com/art/201504/472754.htm
  0x00007f9869034e63: add     $0x8,%rsp
  #实际执行istore把eax里面的变量值放到对应的局部变量槽中,
  #0x1(%r13)这个应该对应的是1,2之类很小的整数所以要movzbl补0,
  #neg可以参考istore_1等指令都是跟着一个很大的数所以要求补码
  0x00007f9869034e67: movzbl  0x1(%r13),%ebx
  0x00007f9869034e6c: neg     %rbx
  0x00007f9869034e6f: mov     %eax,(%r14,%rbx,8)
  #dispatch_next获取istore后面的一条指令并移动r13指针
  0x00007f9869034e73: movzbl  0x2(%r13),%ebx
  0x00007f9869034e78: add     $0x2,%r13
  #dispatch_base跳到下一条字节码,0x7f987310e7e0这个魔数是当前tos下对应的字节码数组地址指向字节码对应的汇编代码。
  0x00007f9869034e7c: movabs  $0x7f987310e7e0,%r10
  0x00007f9869034e86: jmpq    *(%r10,%rbx,8)

6.执行的过程实际上就是不断通过r13拿字节码,然后跳转到TemplateInterpreter::_active_table字节码对应的汇编代码去执行的过程。


类加载

1.在java层面会有ClassLoader的findClass,loadClass等行为,就不做详细描述了。

2.入口 -- Java_java_lang_ClassLoader_defineClass1(ClassLoader.c)

3.解析class文件 -- ClassFileParser::parseClassFile,这一步是个标准的class协议的解析过程,解析生成一个InstanceKlass对象,细节较多但比较好理解

4.把InstanceKlass放入系统字典 -- SystemDictionary::define_instance_class。这一步可以进行eager_initialize但默认是false

5.链接class -- InstanceKlass::link_class_impl,这一步一般是第一次使用该类的时候调用。链接通俗的理解就是加载依赖,实际上这一步会做字节码验证,字节码重写(InstanceKlass::rewrite_class),设置每个方法的解释器入口,编译器入口等等入口(Method::link_method)

6.初始化 -- InstanceKlass::call_class_initializer,调用类的初始化方法



对象创建

1.对应的代码在TemplateTable::_new,对应字节码new的解释执行

2.首先要拿到InstanceKlass,下面这行之前都是在完成这件事
 
  __ movptr(rsi, Address(rsi, rdx,
            Address::times_8, sizeof(ConstantPool)));

3.有快速分配和慢速分配两个路径,有几种情况会进入慢速分配,慢速分配如下
 
  // slow case
  __ bind(slow_case);
  __ get_constant_pool(c_rarg1);
  __ get_unsigned_2_byte_index_at_bcp(c_rarg2, 1);
  call_VM(rax, CAST_FROM_FN_PTR(address, InterpreterRuntime::_new), c_rarg1, c_rarg2);

4.快速路径允许的情况下会尝试TLAB避免多线程争抢
 
  if (UseTLAB) {
    __ movptr(rax, Address(r15_thread, in_bytes(JavaThread::tlab_top_offset())));
    __ lea(rbx, Address(rax, rdx, Address::times_1));
    __ cmpptr(rbx, Address(r15_thread, in_bytes(JavaThread::tlab_end_offset())));
    __ jcc(Assembler::above, allow_shared_alloc ? allocate_shared : slow_case);
    __ movptr(Address(r15_thread, in_bytes(JavaThread::tlab_top_offset())), rbx);

5.不能TLAB就用cas的方式修改堆顶部指针来分配内存
 
    __ cmpxchgptr(rbx, Address(RtopAddr, 0));

6.接下来把对象数据初始化为0以及初始化对象头
 
    // Initialize object fields
    __ xorl(rcx, rcx); // use zero reg to clear memory (shorter code)
    __ shrl(rdx, LogBytesPerLong);  // divide by oopSize to simplify the loop
    {
      Label loop;
      __ bind(loop);
      __ movq(Address(rax, rdx, Address::times_8,
                      sizeof(oopDesc) - oopSize),
              rcx);
      __ decrementl(rdx);
      __ jcc(Assembler::notZero, loop);
    }

    // initialize object header only.
    __ bind(initialize_header);
    if (UseBiasedLocking) {
      __ movptr(rscratch1, Address(rsi, Klass::prototype_header_offset()));
      __ movptr(Address(rax, oopDesc::mark_offset_in_bytes()), rscratch1);
    } else {
      __ movptr(Address(rax, oopDesc::mark_offset_in_bytes()),
               (intptr_t) markOopDesc::prototype()); // header (address 0x1)
    }



内存分配

1.分配的起点 -- CollectedHeap::obj_allocate

2.先尝试在现有的tlab里面分配 -- ThreadLocalAllocBuffer::allocate 直接修改top指针

3.tlab满了,分配一个新的tlab -- CollectedHeap::allocate_from_tlab_slow

4.尝试从堆里面分配一块内存 -- G1CollectedHeap::attempt_allocation 假定在用g1 gc

5.先尝试cas的方式快速分配 -- G1OffsetTableContigSpace::par_allocate_impl

6.慢速加锁分配 -- G1AllocRegion::attempt_allocation_locked

7.尝试扩展新生代分区 -- G1AllocRegion::attempt_allocation_force

8.尝试gc -- G1CollectedHeap::do_collection_pause

9.再尝试分配 -- G1CollectedHeap::attempt_allocation

10.最后尝试 -- G1CollectedHeap::satisfy_failed_allocation通过callback方式执行

参考 JVM源码分析之Java对象的内存分配 《JVM G1源码分析与调优》图3-3


GC过程

DefNew

DefNew是年轻代最简单的gc实现

1.代码入口 -- DefNewGeneration::collect

2.根对象的标识 -- GenCollectedHeap::gen_process_roots gc根有两个来源,一个是来自jvm的根,比如SystemDictionary,代码在GenCollectedHeap::process_roots,一个是来自其它代的引用,代码在GenRemSet::younger_refs_iterate,这里会有一个如何记录分代间引用的问题,稍麻烦一些,后面再写

3.根对象的处理是直接复制到to区 -- FastScanClosure::do_oop_work (1)利用对象头中的信息判断对象是否被处理过oopDesc::is_forwarded (2)to区尝试分配allocate_aligned (3)如果失败尝试晋升Generation::promote (4)老年的尝试分配old_gen->expand_and_allocate (5)实际对象拷贝Copy::aligned_disjoint_words (6)标记拷贝对象old->forward_to

4.递归扫描存活对象 -- FastEvacuateFollowersClosure.do_void 实际上是个广度优先遍历扫描,顺着引用指针搜索,一遍一遍顺序扫描直到没有变化为止ContiguousSpace::oop_since_save_marks_iterate##nv_suffix->klass()->oop_oop_iterate

5.成功,交换存活区域 -- DefNewGeneration::swap_spaces

6.发生晋升失败需要还原移动过的指针 -- DefNewGeneration::remove_forwarding_pointers



TenuredGeneration

TenuredGeneration是最简单的老年代gc实现

1.代码入口 -- TenuredGeneration::collect

2.四个阶段 -- mark_sweep_phase1(标记),mark_sweep_phase2(计算新地址),mark_sweep_phase3(更新指针),mark_sweep_phase4(移动对象到新位置)

3.标记阶段 -- gch->gen_process_strong_roots从gc根开始扫描,不扫描年轻代,MarkSweep::follow_root和ygc一样的处理root,不同的是做mark,而且会处理field里面的引用
InstanceKlass::oop_follow_contents处理fields,然后通过MarkSweep::follow_stack完成递归引用扫描。标记完了以后还会处理各种Reference,做各种资源清理

4.计算新地址 -- SCAN_AND_FORWARD(space.inline.hpp)计算对象新地址保存在对象头,计算对象压缩后的地址的逻辑在CompactibleSpace::forward,计算方式是compact_top += size
这里大致的逻辑是顺序扫碰到活跃的就计算移动后的新位置,碰到没标记的死的就跳过,有个选项是假装放个活对象在死对象的位置来避免过于频繁的压缩移动,放假对象就是set个header

5.更新对象引用地址 -- MarkSweep::adjust_pointer(markSweep.inline.hpp)解析对象的对象头,判断对象头中是否保存着经过压缩后的新地址->InstanceKlass::oop_adjust_pointers(更新引用到新地址)

6.移动所有活跃对象到新位置 -- SCAN_AND_COMPACT(space.inline.hpp)遍历堆从起始位置直到最后一个活跃对象的位置,对于活跃对象调用MarkSweep::live_oop_moved_to移动到新位置


G1 GC

g1 gc引入的概念比较多,从问题解决方案的角度看比较容易理解

如何做到可控的gc停顿时间?

扫描回收完整的代耗时较长,所以引入分区的概念,一次只回收几个分区消耗的时间就可控了,而且只扫描回收已经占满的分区,回收效率也比较高

怎样选择要回收的分区呢?

对于young gen,基于分代假设回收效率会比较高所以全部回收,老年代分区的已使用空间到达一定限度,根据预测停顿时间来选择。选择回收就是加入cset,可以看代码G1CollectorPolicy::finalize_cset

回收一个分区不是要知道所有其它分区对它的引用么?

所以引入了rset的概念(HeapRegionRemSet),对于每个分区记录了所有别的分区到当前分区的引用关系(point in),为什么不是point out呢?因为扫描起来方便,假设要回收一个分区,只要rset里面有记录的对象就不能回收,这些对象就可以作为扫描根,point out就基本没法算了

rset看起来会很大?

rset要描述当前分区所有对象的被引用关系,如果记录的是引用者对象的地址,rset会非常大,需要压缩。首先引入了卡表CardTable的概念,卡表是全局数据结构通过一个字节来描述512字节的状态,之所以不是用一个bit来描述因为bit表达的状态太少,rset里面存的是卡表地址而不是对象地址。然后jvm采用了三种不同的粒度来保存引用关系,取决于对象被引用的频度,代码在OtherRegionsTable::add_reference,其中的细粒度表PRT是用位图的方式描述一个分区的引用状态,记录分区的起始地址以及分区卡表级别的引用状态细节

rset是怎么维护的呢?

1.触发起始点在写屏障,写屏障就是在解析putfield之类的字节码时在之前和之后插入一些动作,看代码oop_store(oop.inline.hpp)

2.把被更新的对象加入全局的dirty card queue,G1SATBCardTableLoggingModRefBS::write_ref_field_work

3.在ConcurrentG1RefineThread线程里定位到卡表对应的512字节,然后遍历里面的对象,找到对象所在分区即被引用者分区,然后把引用关系记录在被引用者分区里面。调用链ConcurrentG1RefineThread::run()->G1RemSet::refine_card->oops_on_card_seq_iterate_careful->G1UpdateRSOrPushRefOopClosure::do_oop_nv->OtherRegionsTable::add_reference

rset是异步更新的,在gc的时候会不会不准?

rset如果不准会漏引用会导致漏扫描,把有引用的对象gc掉,不能接受。所以会有再标记这一步,而且会stw等待引用处理完毕。但是在后面的回收的时候并不是都stw的,为什么不会出问题?个人理解stw标记完毕以后内存已经处于一个一致的状态了,之后并不会产生对已经引用不到会被回收的对象的新的引用了,而内存的分配是往高地址走的,所以之前的那些分区gc的状态并不会随着程序的继续运行而改变

并发标记会出现怎样的并发问题呢?

1.对于gc而言只怕漏标不怕把不存活的标记为存活的

2.标记有三种状态,黑--认为对象和字段都处理过无需再处理,白--对象和字段都没处理过,灰--对象处理过字段还没有处理或没处理完

3.发生漏标是两件事同时发生导致,(1)黑色到白色的新引用因为黑色所以后面不再处理 (2)这个白色对象原来被一些灰色对象持有,在标记的时候这些灰色对象到白色对象的引用都被删除了

4.解决方案也是针对上面两件事,(1)如果黑色对象有新引用要重新置灰,然后可以再再标记过程中达成状态一致 (2)如果引用被删除这个被删除的引用也要放在待标记栈中,这个处理叫SATB,实现放在写屏障取赋值前的旧值(G1SATBCardTableModRefBS:inline_write_ref_field_pre) 如果是黑色的新增引用漏标了,可以在再标记的时候赶上,怕的是这种已有的发生变更,所以处理才这么复杂

5.这个处理算法叫三色标记法,实现上用bitmap保存对象的白和灰两种状态,由于算法是顺序扫bitmap而且标记过程中只扫一次,递归过程中只会写,不会扫,所以可以理解成遍历完了就是置黑了


YGC过程

1.代码入口 -- G1ParTask::work需要在stw后开始,是一个并行的过程

2.处理根集合 -- G1RootProcessor::evacuate_roots,根集合包括线程栈,classloader,系统字典,Universe等等。处理主要是拷贝G1ParCopyClosure::do_oop_work->copy_to_survivor_space,还要遍历对象的每一个字段放到队列里面在后面处理G1ParScanClosure::do_oop_nv

3.处理rset -- G1RootProcessor::scan_remembered_sets,首先更新rset之前没处理完的rset要在这里完成形成一致性的状态(G1RemSet::updateRS),扫描rset,这里rset相当于另一个根是老年代过来的引用(G1RemSet::scanRS),遍历分区中的每个card table(ScanRSClosure::doHeapRegion),遍历card table中的每个对象的每个字段,处理在cset中的引用(HeapRegionDCTOC::walk_mem_region),在cset中的加入后面处理的队列(G1ParPushHeapRSClosure::do_oop_nv),

4.处理之前扫描出的队列(复制) -- G1ParEvacuateFollowersClosure::do_void,处理引用拷贝对象(G1ParScanThreadState::do_oop_evac)

5.其他处理(串行过程) -- jit编译代码位置调整,Reference处理,字符串去重,重建rset(G1CollectedHeap::redirty_logged_cards)等等

Mixed GC

这个阶段和YGC最大的区别是有并发标记,但并没有并发回收。并发标记会标记整个老年代,但只会选择部分分区回收。因为是并发标记,所以标记的时候内存还会高地址增加,会用Next指针来表示并发标记开始的最高内存地址,而Top指针则是当前分配内存的最高内存地址,并发标记开始后到这一轮结束前不会改变Next

1.初始标记(stw) -- 混合收集的初始标记是借用了新生代收集的结果,即新生代垃圾回收后的新生代Survivor分区作为根,所以混合收集一定发生在新生代回收之后,且不需要再进行一次初始标记。但有一小块漏掉的就是根集合能抵达老年代但不能抵达年轻代的部分,所以G1ParCopyClosure::do_oop_work里面有一个逻辑处理这块(G1MarkFromRoot)

2.并发标记的入口 -- 在ygc阶段会通知启动并发标记(G1CollectedHeap::doConcurrentMark),并发标记的线程是ConcurrentMarkThread

3.并发标记扫描根 -- ConcurrentMark::scanRootRegions,扫描根分区列表即survivor分区列表(CMRootRegionScanTasK::work),标记和计数(ConcurrentMark::grayRoot),标记其实是设置一个bitmap的状态(_nextMarkBitMap>parMark(addr))计数主要是统计活跃内存的大小

4.并发标记子阶段 -- ConcurrentMark::markFromRoots,先处理satb buffer(CMTask::drain_satb_buffers),在_nextMarkBitMap里面把引用对置灰(CMTask::make_reference_grey),递归处理引用(CMTask::deal_with_reference),drain_satb_buffers的后续处理(drain_local_queue->_nextMarkBitMap.iterate)
因为标记过程是标记整个堆,只需要从root出发,所以没必要使用rset,实际上标记只使用了satb

5.再标记阶段 -- ConcurrentMark::checkpointRootsFinal,这个阶段的逻辑是类似的(CMRemarkTask::work->G1RemarkThreadsClosure::do_thread)

6.清理子阶段 -- ConcurrentMark::cleanup,交换bitmap相当于状态清0(swapMarkBitMaps),计算分区活跃对象(FinalCountDataUpdateClosure::doHeapRegion),
清理空白分区,也处理被清理影响到其他分区的rset(G1ParNoteEndTask::work),选择要回收的老年代分区(G1CollectorPolicy::record_concurrent_mark_cleanup_end),最终确定要搜集的分区(G1CollectorPolicy::finalize_cset)

7.回收逻辑 --  后面回收的逻辑和ygc完全一样,再标记过程中每个task都有进度指针的,所以不会从头再来一遍,所以会比较快。回收的时候会用上标记的结果判断obj是否存活,其他地方就完全走younggc那一套,但如果完全只依赖rset去判断则效果可能会比较差,一定要用全局扫描的结果,之前有个疑问是好像rset只在ygc里面用到了,实际上在混合gc的回收的时候也会用到

Full GC

full gc不是并发的相对比较简单了,也分串行和并行两种实现

1.首先从Mixed GC失败开始 -- evac失败处理(G1CollectedHeap::remove_self_forwarding_pointers),遍历分区(RemoveSelfForwardPtrHRClosure::doHeapRegion),恢复标记(RemoveSelfForwardPtrObjClosure::do_object)

2.标记活跃对象 -- G1MarkSweep::mark_sweep_phase1,标记根对象,字段入栈(MarkSweep::follow_root),遍历栈上对象(follow_stack)

3.计算对象新地址 -- G1MarkSweep::mark_sweep_phase2 SCAN_AND_FORWARD

4.更新对象引用 -- G1MarkSweep::mark_sweep_phase3 从前往后遍历压缩(SCAN_AND_COMPACT)

5.后处理调整分区大小,重构rset等等

6.并行处理逻辑大多类似,有一个点是一个线程可处理多个分区,可能把多个分区的内容转移到一个分区从而出现空闲分区

Shenandoah和ZGC

问题

g1没有并发回收是因为如果并发回收在对象拷贝的时候会存在两个版本,用户线程可能会同时对两个版本进行读写导致状态错误

Shenandoah

1.在对象内存结构中增加一个Brook指针指向自己的对象头,之所以不放对象头里面是因为对象头太紧凑容易引起较大范围的代码变更

2.复制的时候新对象的Brook指针是指向新对象的地址的,然后用cas把旧对象的Brook指针也指向新地址

3.通过读屏障和写屏障让对旧对象的访问通过Brook指针找到新对象

ZGC

1.zgc的核心变化是使用了染色指针,把标记状态放在引用上而不是被引用对象上,放在引用的42-46位上,副作用就是限制了管理内存大小不能超过4T以及没法在32位系统上用

2.有了染色指针再加上读屏障在访问复制阶段的对象时就能判断需要转到新地址,而且可以直接修正引用的地址,这样就不用像Shenandoah那样每次访问都判断转移一次

3.标记信息全在引用上另外的好处是如果分区在复制的时候清空了,不用等rset这些修正完毕之后才清理掉分区,可以直接处理

4.因为没有分代,每次gc都是清理所以分区所以也不用像g1那样维护rset和使用写屏障,这样系统的吞吐量还会提升。但这样带来的问题是由于gc完成时间比较长,这段时间产生的垃圾没法及时回收



JVM并发基础设施


java线程底层是用的pthread么?

毫无疑问,见代码os::create_thread

jvm自身的并发工具

代码见mutex.cpp,和java标准锁实现区别不大,先cas,spinlock cas,然后enqueue, park 像轻量级锁

为啥轻量级锁不能像偏向锁那样使用threadid,而要拷贝对象头?

对象头可以保存更多的信息,像锁重入这样的场景需要更多的信息支持。

安全点

为什么需要safe point?

系统需要安全状态,比如该flush的变量都flush了,该停止的线程都停止了,去做一些操作。用到安全点的地方最多的是GC和Deoptimization

哪些地方可以放置safe point?

常见的位置有方法返回之前,无界循环回边之前,主要的考量就是程序需要能响应stw的指令但有不能放置过多消耗资源

线程如何被挂起?

调用SafepointSynchronize::begin,这个方法主要就是各种加锁,flush状态,然后等待所有线程停下来。挂起的实现根据java thread不同的状态实现不同,比较经典的一种是通过设置polling page不可读(os::make_polling_page_unreadable)来实现挂起。

Polling Page

1.当UseMembar参数是false的时候用polling page模拟membar的操作

2.原理os::guard_memory->linux_mprotect->SIGSEGV->os::block_on_serialize_page_trap
其实是利用mprotect在内存上监控,在create_stack_guard_pages的时候也使用了类似的技巧

3.对protect memroy的写涉及页表的修改,会引起多核cpu flush storebuffer,得到和volatile类似的效果


协程实现

本来想看一下loom的实现但是弄调试环境的时候坑较多,只好看了quasar来理解协程的原理

1.先看了一个简单的协程实现,有几个关键点 (1)有栈协程需要保存切换eip,esp,其他寄存器,线程栈,使用的是linux ucontext系列函数 (2)协程运行时使用的是共享栈,即运行时先拷贝私有栈的数据到共享栈再使用共享栈当做运行栈,暂停是保存共享栈到私有栈。这种方式的原因是为了节省内存,栈运行时扩容不太容易,共享栈可以设置的大一些

2.在jvm之上实现协程有几个问题需要考虑,(1)怎样退出当前运行方法 (2)怎样保存执行点下次又能重新进入 (3)怎样调度 (4)对lib库需要怎样的使用或者改造

3.通过抛出SuspendExecution来退出当前执行方法,异常被框架捕捉后会做状态保存

4.框架会对所有Suspendable注解的方法做字节码增强,会分析方法中所有的suspend(抛SuspendExecution)的调用,对于这些调用点会把method,local var,以及调用点的位置push stack,到方法恢复的时候在方法前面有个switch case,根据pop stack出来的状态goto到之前的位置继续执行

5.调用上可执行任务都会放到ForkJoinPool,对于有timeout的调用会先放到一个DelayQueue里面等时间到了通过timer调用unpark唤醒,对于没有timeout的调用需要自己抛异常调用unpark,框架提供一个现成的工具类AsyncCompletionStage(需要在自己的线程调用其complete方法),所以对于依赖的lib库一定要实现成异步模式


异常实现机制

1.抛异常的指令是athrow,字节码层面对于异常处理代码正常生成字节码没有特殊指令,但是会有用goto跳转的分支。finally会为每个可能分支增加同样内容的处理字节码。class级别会记录exception table里面有每个try block的范围以及跳转目标

2.TemplateInterpreterGenerator::generate_throw_exception在exception table里面找handler处理,找不到就沿着调用链往上

JVM内存状态


1.入口 -- 64位代码段开始地址0x400000,_start()入口0x4005d0,main()入口0x4006d6

2.内存空间 -- 7fffffffffff用户空间最大值,ffff880000000000 - ffffc7ffffffffff (=64 TB) 内核空间,直接内存映射,不需要32位系统那样的高端内存区。参考 The Memory Layout of a 64-bit Linux Process

3.线程内存使用 -- Linux上多线程进程中,“线程”其实是一组共享虚拟地址空间的进程。只有主线程的栈是按照教科书的经典图示分布,其它线程的栈的位置其实是“随机”的——它们可以由pthread_create()调用mmap()来分配,也可以由程序自己调用mmap()之后把地址传给pthread_create()。既然是mmap()来的,其它线程的栈出现在Memory Mapping Segment的任意位置都不出奇,与用于实现malloc()用的mmap()空间很可能是交错出现的

4.code cache的位置 -- CodeCache::allocate没有指定start,mmap一块默认240m的空间,但一般地址都在0x7fffe1000000这样的较高的位置,注意在pmap里面看起来可能是两块空间因为有一块先commit了

5.堆和metaspace的位置 -- Universe::initialize_heap这句会初始化堆,会先计算一个推荐的位置在e0c00000(4g-heap_size)。Metaspace::global_initialize CompressedClassSpace是紧接着堆后面的位置加上一点对齐分配的  NoKlass Metaspace 这个区域的内存并不是指一块连续内存,而是可以有多块内存链接起来的 


C2编译器

基础知识

逆后序

1.使用场景是比如计算支配节点集合的时候如果按逆后序访问能尽快收敛,在数据流分析中起到加速的作用

2.等价于深度优先排序,或者可以理解成先得到后序然后按和后序完全相反的方向来访问

3.和前序不一样,如果只在树中和前序一样但是在图中就会得到不同的结果,也不是拓扑排序因为可能有环

4.算法实际很简单,就是一个简单的对于每个节点的后继节点的递归再加上一个已访问判断


必经节点树(支配树)和支配边界

1.支配树可以说是编译器后端最重要的数据结构了,在c2中很多地方都用到,不少优化是在支配树上进行的,因为支配树可以表示代码节点间的依赖关系

2.稍简单但效果还不错的算法,(1)只保存直接支配节点通过直接支配节点可以推导出支配树 (2)逆后序遍历,对于每个节点寻找其所有前驱节点的交汇点,这个交汇点就是直接支配节点。参考 构造Dominator Tree以及Dominator Frontier 

3.著名的Tarjan算法,参考虎书,c2里面也用了。总结一下基本思路 (1)也是只存直接支配节点 (2)重点考虑路径分叉的情况,路径不分叉的情况很简单 (3)路径分叉的情况一定是从一个路径上比较靠前的节点分叉,然后汇合到一个路径靠后的节点,那前面这个节点就叫做后面那个节点的半必经节点,我们可以找到一个最靠近根节点的半必经节点,后面分析问题的时候也只需要分析这个最靠近根节点的半必经节点 (4)半必经节点可能就是必经节点,也有可能目标节点和半必经节点间叉进来一个旁路 (5)然后我们通过半必经节点来计算必经节点一种就是半必经节点就是必经节点的,这种情况目标节点到半必经节点间其他节点的半必经节点都没有超出目标节点的半必经节点
(6)如果有超出的,那目标节点的必经节点就和那个超出的节点的必经节点相同 (7)考虑到性能问题,这个算法在找半必经节点的时候还需要一些压缩处理,这个算法的基本思路还是递归化简,整体偏麻烦

4.有了支配树求支配边界比较简单,考虑两种情况(1)n的后继y的直接支配节点不是n那就说明支配不到所以在支配边界(2)n在支配树上的子节点c,考虑c的支配边界上的节点w如果w也不被n支配那w也在n的支配边界上

控制依赖图(CDG)

1.解决的问题是语句A是否必须在B之前执行或者说是否B依赖A,如果直接有A到B的边这个问题很简单,但是有了各种分支跳转之后就比较麻烦了

2.按标准步骤把CFG转换程CDG之后,在逆控制流图中x在y的支配边界中x才直接控制y的执行,所以综合SSA中有使用-定值边,CDG中有A->B的路径两种情况A必须在B之前执行

3.解决了依赖问题之后就可以做激进的死代码删除或者并行编译优化

静态单赋值形式(ssa)

1.变量的赋值和使用关系是个多对多的关系,有了ssa形式就变成了一对多关系。简单的说ssa形式就是为了性能,当然也会简化后续各种算法

2.普通CFG转换程ssa主要就两步,插入phi节点和变量重命名

3.插入phi节点引入了支配边界的概念,简单说就是在一个节点定义了变量那么在该节点的支配边界的每个节点都需要插入一个该变量的phi函数,变量重命名算法相对比较简单


Sea of Nodes(理想图)

1.介绍Sea of Nodes比较详细全面的是Cliff Click的两篇论文,A Simple Graph-Based Intermediate Representation(这篇是详细介绍),From Quads to Graphs: An Intermediate Representation's Journey(这篇是ssa演化史)

2.sea-of-nodes和一般ssa有两个较大差别 (1)取消了变量名,直接使用变量的值作为节点,这样简单的常量传播直接都变成了no op (2)传统表示一般有两层,上面一层是cfg表示控制流,下面一层是基本块包含实际的指令代表数据流,sea-of-nodes简化了表示引入了region node来代表基本块

3.表达if node后面的跳转可以把信息放到边上但这样会让边承载信息变得复杂所以引入了projection node,接受if node产生的多值选择一个作为输出。

4.ssa形式下一个变量在不同分支可能分裂成不同变量,再汇聚的时候需要引入phi函数,所以引入phi node来表达变量汇聚

5.MergeMemNode,这里不能直译理解,这里merge的是不同alias type下的mem node,alias type涉及到type-based alias analysis,是一种编译优化手段

C2整体流程

记录印象中比较重要的过程,整体按顺序但不绝对

1.入口 -- Compile::Compile

2.类型分析 -- ciTypeFlow::flow_types 解析字节码,生成栈和局部变量的type状态,然后在解析生成sea nodes的时候把type和node关联上

3.解析字节码生成sea_of_nodes -- ParseGenerator::generate

4.理想图局部优化 -- PhaseIterGVN::optimize 比如在AddNode里面把(x+1)+2转换成x+(1+2)然后x+3,这个过程是穿插在理想图的各种优化(机器无关优化)始终的

5.Gloval Value Numbering(gvn) -- 发现并消除等价计算,可以将 GVN 理解为在 IR 图上的公共子表达式消除(PhaseValues::hash_find_insert)

6.内联 -- Compile::inline_incrementally

7.逃逸分析 -- ConnectionGraph::do_analysis

8.标量替换 -- PhaseMacroExpand::scalar_replacement 做的事情很简单,把对应obj的field全部放到一个新的node上面并关联进去,并删除obj

9.循环优化 -- PhaseIdealLoop::build_and_optimize循环优化的手段和细节都非常多

10.条件常量传播(ccp) -- PhaseCCP::analyze PhaseCCP::transform_once 

11.指令选择 -- Matcher::match

12.Global Code Motion -- PhaseCFG::do_global_code_motion这一步重排序特征明显

13.Implicit Null Checks -- PhaseCFG::implicit_null_check

14.寄存器分配 -- PhaseChaitin::Register_Allocate

15.peephole优化 -- PhasePeephole::do_transform 调用每个MachNode的peephole方法做局部优化

16.生成机器码 -- Compile::fill_buffer


ciTypeFlow::flow_types


1.该过程会生成基本块并识别循环结构,当然更重要的是会生成apply该方法后栈和局部变量的type lattice状态

2.该过程是在做数据流分析,是深度优先遍历,会逐个block遍历(flow_block),然后逐个字节码遍历(StateVector::apply_one_bytecode),像个解释器但是由于没有input参数所以只是做类型分析

3.flow_block方法根据incoming state解析方法字节码,并把变更后的state推送到后继节点,遇到trap会退出,推送的其实是当前节点的local和stack里面对应的typelattice

4.计算类型的时候会使用type lattice经典的meet操作(StateVector::type_meet_internal),比如如果两个普通类就是找共同的超类

5.apply_one_bytecode之后根据状态可能会跳到Block::successors,会根据之前apply字节码的状态生成新的基本块(block)

6.build_loop_tree 根据访问顺序关系发现回边构建loop节点,并处理一些其他属性

解析字节码生成sea_of_nodes

1.主线代码流ParseGenerator::generate->Parse::Parse->Parse::do_all_blocks->Parse::do_one_block->Parse::do_one_bytecode

2.parse过程会生成局部变量,栈等结构,但是里面放的都是cfg node,cfg node结构会比较复杂里面的if else,变量值这些都是节点,要运行时才知道具体怎么走,一些简单的push pop jvm字节码相当于在这一步已经执行过了

内联

1.在解析字节码的时候碰到多态方法调用会判断是否要内联(Parse::do_call),判断的一个重要依据是该方法是否是多态方法的唯一实现(Dependencies::find_unique_concrete_method)。还有一个判断在InlineTree::try_to_inline,主要判断调用深度方法大小等

2.内联的实际逻辑还是会调用ParseGenerator::generate,本质上inline就是parse字节码,生成sea-of-nodes

逃逸分析

1.逃逸分析有篇paper参考 Escape Analysis for Java

2.逃逸分析的目标是分析对象是方法局部的,还是会在方法间传递(线程局部),或者是全局的

3.逃逸分析的作用 (1)可以做到栈上分配对象,避免堆上分配的并发开销(这个tlab也能做到,但tlab还是在堆上分配),也可以不用gc (2)也可能做标量替换优化就是把对象拆成一堆值,个人理解就是所有访问field的地方改成直接访问对应的值 (3)运行时还可以去掉一些不不要的加锁,比方说对象的方法是加锁的,调用的时候就可以忽略掉

4.逃逸分析的大致过程,方法内部比较简单,工作表算法,每个对象或者引用把逃逸状态扩散到赋值或者成员变量引用,跨方法调用就是对参数作扩散,也是通过赋值和成员变量引用扩散逃逸状态

5.逃逸分析之前先判断是否需要分析,有内存分配,锁,和valueOf调用逃逸分析才会产生收益,就这三种调用会使用marco node(ConnectionGraph::has_candidates)

6.分析过程(compute_escape)中不断把新节点加入连通图(add_node_to_connection_graph),如果碰到了方法调用(add_call_node)就需要对方法做字节码分析(BCEscapeAnalyzer::BCEscapeAnalyzer)

7.字节码分析过程中(iterate_one_block),比如碰到Bytecodes::_putfield如果put的是object或者array就可能产生global escape(set_global_escape)

8.扫描完所有的sea-of-nodes构造了基本连通图后,会扩散逃逸状态,补全连通图(complete_connection_graph),对于所有的不逃逸节点(non_escaped_worklist)判断不能标量替换的6种情况,设置能否标量替换(adjust_scalar_replaceable_state)

9.根据连通图信息优化理想图,比如锁消除,优化storestore barrier,对象比较的一些case简化成常量(optimize_ideal_graph)

10.对于不逃逸的allocation可能是CheckCastPP创建新的instance type并且传播,可能也会产生alias type,这个动作应该是为标量替换做准备(split_unique_types)

循环优化

有两篇文章可以参考 openjdk wik stackoverflow

代码过程

1.按逆后序给cfg每个节点生成关联IdealLoopTree节点(PhaseIdealLoop::build_loop_tree)

2.构建必经节点树(PhaseIdealLoop::Dominators),这里用的是tarjan算法

3.给每个节点计算最接近的控制节点(build_loop_early),找到支配树上深度最大的控制节点,所有in里面最深的(get_early_ctrl),上提昂贵的ctrl节点(get_early_ctrl_for_expensive)

4.induction variable subsitution,(PhaseIdealLoop::replace_parallel_iv)寻找和i++的i关联的变量并且转化成i的形式,可能去除外部变量依赖让循环更好做并行优化

5.计算所有out最早的公共父节点也就是这个节点最深能放到哪(PhaseIdealLoop::get_late_ctrl)

6.上提昂贵节点的控制节点,前提是不能执行得更频繁,基本逻辑是对于完全相同的节点把控制节点替换成这些节点的控制节点中最支配的那个,expensive node看来都是那些复杂数学运算    (process_expensive_nodes)

7.对于+-运算把不变量放一起规范化,不变量这里不是常量而是不随循环变的(reassociate_invariants)

8.把和地址运算相关的不变量放到表达式后面和其它几个操作(remix_address_expressions)

9.把当前节点替换成phi节点,phi节点的branch x是n的clone,所以是split,然后对x做简化如果有足够的收益替换就成立,分裂的分支数是n的region的in的数量(split_thru_phi)

10.找到所有的if_proj节点,对其中符合模式的pred节点做提升,个人理解就是在predicate_proj的位置对每一个if_proj生成一个外部的new_if(loop_predication)

11.数组赋值模式转化程Arrays.fill(do_intrinsify_fill)

12.对于非counted loop把内部的判断外提,但是要执行的语句只是clone所以是particial peel,细节参考注释的图就ok,和do_peeling不同的是没有循环不变测试的要求(partial_peel)

13.把循环第一次迭代的if外提,逻辑看图形就可以了。peel的条件是是否有循环不变量的if。(do_peeling)

14.同样是循环里面有循环不变测试,和peel不同的是这个测试不是循环退出测试,做法是测试外提,循环体拷贝到true和false两个分支稍有变化(do_unswitching)

15.循环展开(counted loop),只做一步循环数/2(do_unroll)

16.生成rce的前置后置循环(insert_pre_post_loops)

17.调整limit删除if(do_range_check)

18.减少trip_counter的使用范围的优化(reorg_offsets)

Range Check Elimination

把循环分解成前段,中段和后段,这样中段就不用做数组范围检查,让中段尽量长。PhaseIdealLoop::do_range_check

Loop Predication

其实就是把循环里面的判断语句(比如if)外提,主要约束就是必须有那些循环不变量 IdealLoopTree::loop_predication可以作为range check elimination的替代而且c2使用的就是loop predication

Array Filling 

在循环中把数组赋值自动转换成Arrays.fill,后者可以使用slp进一步优化。参考 On Arrays.fill, Intrinsics, SuperWord and SIMD instructions

Loop unswitching

循环内的if等判断外提,并且循环复制一份到不同分支,这样if只执行一次。参考 https://en.wikipedia.org/wiki/Loop_unswitching

Implicit Null Checks

有很多nullcheck,包括程序员自己写的和自动生成的,如果发生概率很低就可以直接去掉,可以减少test, je两个指令,然后后面加上一个uncommon trap回到优化前的代码。

Superword Level Parallelism(SLP)


2.实际上是simd指令的一种应用,经典case是把1-16的循环变成1-4的循环展开,然后循环内部优化程simd指令,一个指令算4次运算

3.这种技术有个要求是在某个位置操作数的内存地址需要是相邻的,比方在一个数组里面。其它的操作数个人理解可以打包放到一个寄存器里面,比如128位的寄存器放4个32位的数但这样可以需要4个指令打包操作数,也会有消耗

4.slp编译的核心目标是对指令进行分组,比如分4个组就可以用上并行度4的simd,分组大致的过程就是先找出操作数有内存相邻的指令,然后分析指令的下游形成几个组

5.slp优化的代码在SuperWord::SLP_extract,流程是,类型处理(compute_vector_element_type),把内存操作两两打包(find_adjacent_refs),到in和out里面添加打包(extend_packlist),相邻的pack连接起来(combine_packs),load只是换成pack开始或者结束的mem_state,store顺着last的in往上找,如果不在pack里面的就往前或者往后移动(co_locate_pack),生成LoadVectorNode,StoreVectorNode等等,整个过程重点处理mem dependency(output)

条件常量传播

1.算法基本描述可以参考论文 Constant propagation with conditional branches 组合分析可以参考论文 Combining Analyses, Combining Optimizations 简单了解可以参考 知乎回答

2.如果不考虑if等分叉的cp算法,把每个节点的lattice信息顺着ssa传播,循环到不再改变就ok,其实也很简单,比如一个加法的每个in节点的lattice都是constant那这个加法就是constant

3.考虑上if等分叉的情况,加上一个cfg图来加速对分支的判断,遇到分支的时候看看每个分支的lattice情况,如果有常量的而且是可执行状态就往下传播,如果是不确定的情况也要传播,不可执行的就可以忽略

4.对于赋值类型的节点,往ssa worklist上加,对于if-else类型的节点往cfg worklist上加

5.combining analysis,这篇论文提供的新内容是,对于cp和unreachable code elimiation两套体系都可以有各自的lattice但这样有些情况的优化做不了,但是combine两个lattice也就是
在每个节点同时算两个框架的lattice信息,并定义两个两种lattice的转换函数,传播收敛之后就能优化掉之前做不了的优化

6.PhaseCCP::PhaseCCP(入口)->PhaseCCP::analyze(主要调用n->Value算一下type)->PhaseCCP::transform_once(主要是类型的处理,逻辑处理应该都包含在transform,ideal等地方了)

指令选择


2.指令描述文件(ad)可看x86_64.ad和assembler_x86.cpp,描述文件里面定义了指令序列匹配怎样的ir树形结构以及对应指令的cost供指令选择算法使用

3.iburg算法整个过程实际上是把中间表示ir组织成一颗颗的树,然后从叶子开始和指令选择规则做匹配

4.对于每个叶子拿它对应的op操作和对应的规则做匹配,每个规则的右边是匹配条件,每个匹配都有可能是个多选项,多选来源一个是可能多个规则合适,另一个来源是链式规则比如disp->reg->stmt,整个链上的非终结符都可能匹配的上。所以需要一个动态规划算法

5.算法是对ir组成的语法树做从底向上的动态规划算法,树节点+该节点选择的匹配项 构成动态规划里面的一个状态,算法不复杂但优化比较麻烦,各种bit压缩

6.Compile::Code_Gen(入口)->Matcher::xform(主要处理match的大流程)->match_tree(这里应该做了动态规划)->Matcher::Label_Root(标记一个节点,先递归下降到子节点,然后返回父节点,标记是填充状态数组主要是opcode->cost,有些cost的计算需要根据子节点的cost,每个节点的数组的下标都是所有可能的指令,所以应该是个动态规划算法) (dfa的过程是根据node->opcode做switch case,dfa是根据ad file生成的,switch case里面再根据子节点的状态去判断设置状态,所以估计可能出现opcode对应多种满足match条件的可能性,这里生成的比较重要的数据结构是state)->ReduceInst(根据state生成机器码节点,主要逻辑在递归处理参数节点这些)->match_sfpt(和match_tree对应处理safepoint节点,其实主要还是调用match_tree)

Global Code Motion


2.gcm相关的优化有循环外提,变量定义下推等等,把代码尽量往循环外面提(向上),然后又尽量减少变量作用域(向下)。

3.分两步,第一步是把每个指令沿着支配树上提,一直提到和它最深的一个input同级,第二步把指令沿着支配树下降,下降到所有依赖这个指令的后继的最浅公共节点。

4.最后一步还要考虑循环深度,在上提和下沉的范围区间内选择最小的循环深度。

5.相关的代码 PhaseCFG::build_cfg(ideal graph插入一些region,goto等节点,主要是生成了一些block节点并把这些block节点连接成cfg,idea graph只有region节点没有block节点)->PhaseCFG::build_dominator_tree(tarjan算法)->CFGLoop::compute_freq(计算每个block的概率,关键逻辑是遍历cfg的时候把当前的频率带到后继节点相加这样处于公共路径上的节点的概率就高)->global_code_motion(gcm入口)->
schedule_pinned_nodes(对于pin的node,找到node的input,是blockstart的input,对应的block并关联)->
PhaseCFG::schedule_early(对于所有节点深度优先遍历,尽量提前寻找最早能放进的block,寻找方式是找节点所有input最深的block,然后把节点塞到这个block中)
->compute_latencies_backwards(计算所有节点的延迟,后序遍历所有节点,对于每个节点查找当前节点的latency,并且查找该节点每个def对应的delta相加传播到def节点)
->schedule_late(沿着支配树下降)->insert_anti_dependences(增加load到store的反向边便于追溯,用到alias_index,store->add_prec(load)主要这句)
->hoist_to_cheaper_block(沿着所有use的lca往dom上找,直到当前节点的block,找frequency最小的block)

Implicit Null Checks


2.有很多nullcheck,包括程序员自己写的和自动生成的,如果发生概率很低就可以直接去掉,可以减少test, je两个指令,然后后面加上一个uncommon trap回到优化前的代码

3.代码在PhaseCFG::implicit_null_check,流程是找到一个合适的位置插入一个MachNullCheckNode节点,然后把之前的check代码删掉

寄存器分配

参考文档 

论文 REGISTER ALLOCATION & SPILLING VIA GRAPH COLORING 文档 The C2 Register Allocator 寄存器分配是个活跃领域所以还有很多论文,实在没时间深入了

虎书上的图着色算法

1.算法除了给每个指令指派寄存器之外还起到删除无用mov指令族的作用

2.通过数据流分析得到CFG

3.构造冲突图,逆序遍历cfg每条指令,指令中的每个def变量和所有live变量添加冲突边,live变量列表在指令分析过程中会根据def和use变量调整。live的定义是def到最后一个use这段都是活跃的,如果有多个def,那么     活跃区间就在多个def到对应def到最后一个use之间分成很多小段。由于live分析是逆序的,所以可以理解一些预着色的节点如果一直没被用到甚至在冲突图中就可以不出现。

4.简化,相邻节点数少于K(寄存器数量,又叫度数)而且和mov无关的节点可以直接移除(后面可以随便指定一个可用寄存器),因为存在递归不变式

5.合并,对于mov指令相关的两个变量如果满足一些条件(合并之后度数>K的节点数小于K也就是合并后的节点可被简化)可以直接合并简化冲突图

6.冻结,没法简化和合并之后可以把度数较低的mov节点冻结放弃合并优化然后尝试简化操作

7.如果还存在一些度数大于K的节点选择溢出,用内存去保存变量,改写源代码把变量操作变成存储地址操作,并为这个存储地址的每一次def和use创建新的临时变量,这样新的临时变量的范围会很小,后面就容易被处理掉。

8.着色,根据约束选择一个现在可用的颜色就可以了,没有很特殊的算法,溢出之后重新走前面从4开始的步骤

9.有些寄存器比如bp,sp,或者保存参数的寄存器,默认已经有绑定了,称作预着色节点。预着色节点不能简化和溢出,但是可以用新的临时变量+mov指令保存和恢复来减小范围,新的临时变量可以溢出。预着色节点也可以和其他节点合并。虎书的代码处理里面只在合并这一步有对预着色节点的处理。

10.如果着色算法的输入是表示式树算法会简单很多,只要从叶子节点上自底向上随意指定颜色就可以了,然后还可以用动态规划做优化。不太了解现实中什么情况会是这个场景(纯函数式?)。

11.chaitin的论文里面增加了选择溢出寄存器的算法,选择cost最小的逻辑寄存器去溢出,cost计算考虑和这个寄存器相关的def和use节点,def和use的cost是它们的执行频率

C2实现

PhaseChaitin::Register_Allocate(入口)->de_ssa(给每个node初始化一个虚拟register number,通过liverange表示,这个就是liverange的真实抽象)->
gather_lrg_masks(遍历每个指令做liverange的一些信息收集设置一些标志位,比如是不是float,需要多少regs等等)->
PhaseLive::compute(逆序,block内指令增加def,每个in增加use,把use传播到in放到live里面)->
stretch_base_pointer_live_ranges(查看所有gc point延伸liverange到gc point,对每个block每个node如果n->jvms存在说明是safepoint,该节点所以的in定义的range都加入liveout)->
live.compute(重新计算一遍)->
build_ifg_virtual(实际构建冲突图,和虎书的描述基本一致)->
PhaseConservativeCoalesce::coalesce(合并冲突图)->lrg_union(合并操作)->
build_ifg_physical(和前面主要的区别是寄存器都是物理真实的,copy也是真实的,先搞一遍虚拟的激进的merge个人理解是尽量先合并move优化代码,在后面再考虑染色)->
interfere_with_live(到这句才开始建冲突图)->
Split(把range拆分为较小的range,其实spill也是在这里做了,细节多)->
Simplify(和虎书上描述的简化过程基本一致)->
Select(给所有节点上色实际分配)->
fixup_spills(cisc指令集的spill指令转换成FramePtr + offset形式)

生成机器码

Compile::Output(入口)->Scheduling::AddNodeToBundle(逆序所有node,放到一个个bundle里面,受制于体现拓扑结构的latency)->
do_liveness(对每个节点计算寄存器liveness,方法还是用def和use做加减)->
OopFlow::build_oop_map(为node生成oopmap并设置vmreg)->
fill_buffer(简单看就是遍历每个node调用emit,再加上一些method地址,exception_handler地址)

Type Based Alias Analysis

1.同一个地址可能会被多个指针指向(指针别名)而且每个指针的使用可能不同,如果知道两个变量是否指向同一个地址可以做一些编译优化,所以需要alias analysis。参考 维基百科

2.把程序的内存访问划分成不同的alias classes,不同的class之间不可能别名,强类型语言不同的type在不同的class,对object field, array都有一些规则

Type Lattice

1.参考Cliff Click讲type lattice的三篇文章 1 2 3

2.ccp的场景,判断一个变量是否是常量,通过type lattice保留尽量多的变量是否是常量的信息。

3.常见的场景还有数值判断,null判断,对象类型判断(用于去掉虚函数调用变成inline的)

4.type lattice分成top(可以是任何常量),具体value,bottom(不是常量)。用于其他维度的时候(比如是否null,对象类型)可能会更复杂一些派生出一些子类型。

5.有三种操作meet(对应if else汇聚和while回边),dual(类似于取反或者负数操作),join(用在if条件里面同时满足多个条件)。meet和join看起来相似但不是一回事,meet是并集join是交集

6.type lattice满足对称性,交换律和结合律。在比较复杂的场景的meet可能会产生二义,Hashtable:top meet String:exact:not_null,可能会有bug,但少见。多个冒号代表多个维度

7.type lattice从理论上看有点复杂,但是从实用角度想,多个领域都有通过信息不断获取强化类型的场景,把这些抽象在一起就是type lattice了


Class Hierarchy Analysis(CHA)

1.首先在类结构体系里面找method(find_monomorphic_target),如果是唯一的实现ok了

2.否则看变量actual_receiver_is_exact来自type lattice信息,如果true,直接resolve_invoke出method

其他比较杂的记录

cpu亲和性


StackYellowPages

-XX:StackYellowPages,-XX:StackRedPages,-XX:StackShadowPages线程栈尾预留,当rsp到达这些预留空间位置的时候会有对应的处理,防止虚拟机挂掉。参考 https://www.jianshu.com/p/debef4f69a90

Touch

Linux系统并不会对新分配未touch的虚拟内存映射任何物理页面,以read方式首次touch时会映射共享的zeropage页面,以write方式首次touch时会分配新的物理页面并映射之,以write方式在首次read touch之后touch时,写时拷贝会分配新的物理页面并映射之

Oprofile

是一种细粒度的工具,可以为指令集或者为函数、系统调用或中断处理例程收集采样

为啥用metaspace替换perm gen?

1.class和classloader生命周期趋同一起回收效率更高所以给每个classloader一个metatrunk 参考 https://blog.csdn.net/jijijijwwi111/article/details/51564271

2.permgen size不好设置

3.模型上permgen不太对,类的元信息不应该是对象,就应该抽象出来,而且jrocket是没有permgen的

4.gc实现不用每个都搞一个permgen iterator了

5.gc生命周期堆和metaspace解耦

6.所以总体感觉还是一个模型上的变化

primary super和secondary super

用于快速类型判断 参考instanceOf在多核环境中的并发问题 

debug时查看Symbol的办法

class_name->as_C_string() 报assertion异常的时候用SuppressErrorAt=/resourceArea.hpp:63

hsdb

一个比较有用的jvm debug工具

intrinsic methods

编译器内建方法,主要用于性能和诊断,比如jvm的System.currentTime Math.log Unsafe.swap等等

uncommon trap

对编译器认为不太可能走到的分支做的一种处理,如果被命中通常会重新解释执行,作用是节省编译时间和生成代码的大小

jsr和ret指令

这两个是给子程序用的,而子程序和方法调用是两回事,子程序处理finally的过程,在比较新的jvm中这两指令已经不用了

reducible loop

只有一个entry point的循环叫reducible loop可以被分解成前向边和回边,一般只有goto或者编译器优化会产生irreducible loop

基本块

只有一个入口和一个出口的指令序列

oop模型

见代码oop.hpp instanceKlass.hpp 参考文章 深入探究 JVM | klass-oop对象模型研究

jvm的方法栈帧和native的一样么?

本质上一回事,不过native一般c语言编译堆栈管理惯例按c的走而jvm方法也是有栈管理那一套,不过是用jvm生成的汇编去管理,细节上是否和c那一套完全一样不确定

编译后的代码是放到代码段的么?

应该做法不同,code cache应该是自己开辟的一块内存而不是整个程序编译的时候那种静态的

参考资料

除了笔记中记录的链接之外还有两本书

《JVM G1 源码分析和调优》
《深入解析Java虚拟机HotSpot》