golang - 一些数据结构的底层实现

主要是一些数据结构的底层实现

Channel 的底层实现

前言

  • channel是Golang在语言层面提供的goroutine间的通信方式,比Unix管道更易用也更轻便。channel主要用于进程内各goroutine间通信,如果需要跨进程通信,建议使用分布式系统的方法来解决。

  • 本章从源码角度分析channel的实现机制,实际上这部分源码非常简单易读。

chan数据结构

  • src/runtime/chan.go:hchan定义了channel的数据结构:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    type hchan struct {
    qcount uint // 当前队列中剩余元素个数
    dataqsiz uint // 环形队列长度,即可以存放的元素个数
    buf unsafe.Pointer // 环形队列指针
    elemsize uint16 // 每个元素的大小
    closed uint32 // 标识关闭状态
    elemtype *_type // 元素类型
    sendx uint // 队列下标,指示元素写入时存放到队列中的位置
    recvx uint // 队列下标,指示元素从队列的该位置读出
    recvq waitq // 等待读消息的goroutine队列
    sendq waitq // 等待写消息的goroutine队列
    lock mutex // 互斥锁,chan不允许并发读写
    }
  • 从数据结构可以看出channel由环形队列、互斥锁、类型信息、goroutine等待队列组成,下面分别说明其原理。

环形队列

  • chan内部实现了一个环形队列作为其缓冲区,队列的长度是创建chan时指定的。

  • 下图展示了一个可缓存6个元素的channel示意图:

  • dataqsiz指示了队列长度为6,即可缓存6个元素;
  • buf指向队列的内存,队列中还剩余两个元素;
  • qcount表示队列中还有两个元素;
  • sendx指示后续写入的数据存储的位置,取值[0, 6);
  • recvx指示从该位置读取数据, 取值[0, 6);

等待队列

  • 从channel读数据,如果channel缓冲区为空或者没有缓冲区,当前goroutine会被阻塞。

  • 向channel写数据,如果channel缓冲区已满或者没有缓冲区,当前goroutine会被阻塞。

  • 被阻塞的goroutine将会挂在channel的等待队列中:

  • 因读阻塞的goroutine会被向channel写入数据的goroutine唤醒;

  • 因写阻塞的goroutine会被从channel读数据的goroutine唤醒;

  • 下图展示了一个没有缓冲区的channel,有几个goroutine阻塞等待读数据:

  • 注意,一般情况下recvq和sendq至少有一个为空。只有一个例外,那就是同一个goroutine使用select语句向channel一边写数据,一边读数据。

类型信息

  • 一个channel只能传递一种类型的值,类型信息存储在hchan数据结构中。
    • elemtype代表类型,用于数据传递过程中的赋值;
    • elemsize代表类型大小,用于在buf中定位元素位置。

  • 一个channel同时仅允许被一个goroutine读写,为简单起见,本章后续部分说明读写过程时不再涉及加锁和解锁。

channel读写

创建channel

  • 创建channel的过程实际上是初始化hchan结构。其中类型信息和缓冲区长度由make语句传入,buf的大小则与元素大小和缓冲区长度共同决定。

  • 创建channel的伪代码如下所示:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    func makechan(t *chantype, size int) *hchan {
    var c *hchan
    c = new(hchan)
    c.buf = malloc(元素类型大小*size)
    c.elemsize = 元素类型大小
    c.elemtype = 元素类型
    c.dataqsiz = size

    return c
    }

向channel写数据

  • 向一个channel中写数据简单过程如下:
  1. 如果等待接收队列recvq不为空,说明缓冲区中没有数据或者没有缓冲区,此时直接从recvq取出G,并把数据写入,最后把该G唤醒,结束发送过程;
  2. 如果缓冲区中有空余位置,将数据写入缓冲区,结束发送过程;
  3. 如果缓冲区中没有空余位置,将待发送数据写入G,将当前G加入sendq,进入睡眠,等待被读goroutine唤醒;
  • 简单流程图如下:

从channel读数据

  • 从一个channel读数据简单过程如下:
  1. 如果等待发送队列sendq不为空,且没有缓冲区,直接从sendq中取出G,把G中数据读出,最后把G唤醒,结束读取过程;
  2. 如果等待发送队列sendq不为空,此时说明缓冲区已满,从缓冲区中首部读出数据,把G中数据写入缓冲区尾部,把G唤醒,结束读取过程;
  3. 如果缓冲区中有数据,则从缓冲区取出数据,结束读取过程;
  4. 将当前goroutine加入recvq,进入睡眠,等待被写goroutine唤醒;
  • 简单流程图如下:

关闭channel

  • 关闭channel时会把recvq中的G全部唤醒,本该写入G的数据位置为nil。把sendq中的G全部唤醒,但这些G会panic。

  • 除此之外,panic出现的常见场景还有:

    • 关闭值为nil的channel
    • 关闭已经被关闭的channel
    • 向已经关闭的channel写数据

Interface 的底层实现

  • 参考链接
  • golang中的接口分为带方法的接口空接口
    • 带方法的接口在底层用iface表示。
    • 空接口的底层则是eface表示。

接口的原型

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
//runtime/runtime2.go

//非空接口
type iface struct {
tab *itab
data unsafe.Pointer
}
type itab struct {
inter *interfacetype
_type *_type
link *itab
hash uint32 // copy of _type.hash. Used for type switches.
bad bool // type does not implement interface
inhash bool // has this itab been added to hash?
unused [2]byte
fun [1]uintptr // variable sized
}

//******************************

//空接口
type eface struct {
_type *_type
data unsafe.Pointer
}

//========================
//这两个接口共同的字段_type
//========================

//runtime/type.go
//_type这个结构体是golang定义数据类型要用的。
type _type struct {
size uintptr
ptrdata uintptr // size of memory prefix holding all pointers
hash uint32
tflag tflag
align uint8
fieldalign uint8
kind uint8
alg *typeAlg
// gcdata stores the GC type data for the garbage collector.
// If the KindGCProg bit is set in kind, gcdata is a GC program.
// Otherwise it is a ptrmask bitmap. See mbitmap.go for details.
gcdata *byte
str nameOff
ptrToThis typeOff
}

iface