最近没事做，临近期末，随便翻点源码，发现go竟然有个container包，以前从来没用过，里面有一个简单的list和一个heap，先贴出源码研究一下



![image.png](/static/img/f41663ef8809e03d839b42799e5dcef9.image.webp)
```go
// Copyright 2009 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

// Package list implements a doubly linked list.
//
// To iterate over a list (where l is a *List):
//
//	for e := l.Front(); e != nil; e = e.Next() {
//		// do something with e.Value
//	}
package list

// Element is an element of a linked list.
type Element struct {
	// Next and previous pointers in the doubly-linked list of elements.
	// To simplify the implementation, internally a list l is implemented
	// as a ring, such that &l.root is both the next element of the last
	// list element (l.Back()) and the previous element of the first list
	// element (l.Front()).
	next, prev *Element //前后向指针

	// The list to which this element belongs.
	list *List

	// The value stored with this element.
	Value any
}

//
// List represents a doubly linked list.
// The zero value for List is an empty list ready to use.
type List struct {
	root Element // sentinel list element, only &root, root.prev, and root.next are used
	len  int     // current list length excluding (this) sentinel element
}


// Next returns the next list element or nil.
func (e *Element) Next() *Element {
	if p := e.next; e.list != nil && p != &e.list.root {
		return p
	}
	return nil
}

// Prev returns the previous list element or nil.
func (e *Element) Prev() *Element {
	if p := e.prev; e.list != nil && p != &e.list.root {
		return p
	}
	return nil
}


// Init initializes or clears list l.
func (l *List) Init() *List {  //前后指针指向自己
	l.root.next = &l.root
	l.root.prev = &l.root
	l.len = 0
	return l
}

// New returns an initialized list.
func New() *List { return new(List).Init() }

// Len returns the number of elements of list l.
// The complexity is O(1).
func (l *List) Len() int { return l.len }

// Front returns the first element of list l or nil if the list is empty.
func (l *List) Front() *Element {
	if l.len == 0 {
		return nil
	}
	return l.root.next
}

// Back returns the last element of list l or nil if the list is empty.
func (l *List) Back() *Element {
	if l.len == 0 {
		return nil
	}
	return l.root.prev
}

// lazyInit lazily initializes a zero List value.
func (l *List) lazyInit() {
	if l.root.next == nil {
		l.Init()
	}
}

// insert inserts e after at, increments l.len, and returns e.
func (l *List) insert(e, at *Element) *Element {
	e.prev = at
	e.next = at.next
	e.prev.next = e
	e.next.prev = e
	e.list = l
	l.len++
	return e
}

// insertValue is a convenience wrapper for insert(&Element{Value: v}, at).
func (l *List) insertValue(v any, at *Element) *Element {
	return l.insert(&Element{Value: v}, at)
}

// remove removes e from its list, decrements l.len
func (l *List) remove(e *Element) {
	e.prev.next = e.next
	e.next.prev = e.prev
	e.next = nil // avoid memory leaks
	e.prev = nil // avoid memory leaks
	e.list = nil
	l.len--
}

// move moves e to next to at.
func (l *List) move(e, at *Element) {
	if e == at {
		return
	}
	e.prev.next = e.next
	e.next.prev = e.prev

	e.prev = at
	e.next = at.next
	e.prev.next = e
	e.next.prev = e
}

// Remove removes e from l if e is an element of list l.
// It returns the element value e.Value.
// The element must not be nil.
func (l *List) Remove(e *Element) any {
	if e.list == l {
		// if e.list == l, l must have been initialized when e was inserted
		// in l or l == nil (e is a zero Element) and l.remove will crash
		l.remove(e)
	}
	return e.Value
}

// PushFront inserts a new element e with value v at the front of list l and returns e.
func (l *List) PushFront(v any) *Element {
	l.lazyInit()
	return l.insertValue(v, &l.root)
}

// PushBack inserts a new element e with value v at the back of list l and returns e.
func (l *List) PushBack(v any) *Element {
	l.lazyInit()
	return l.insertValue(v, l.root.prev)
}

// InsertBefore inserts a new element e with value v immediately before mark and returns e.
// If mark is not an element of l, the list is not modified.
// The mark must not be nil.
func (l *List) InsertBefore(v any, mark *Element) *Element {
	if mark.list != l {
		return nil
	}
	// see comment in List.Remove about initialization of l
	return l.insertValue(v, mark.prev)
}

// InsertAfter inserts a new element e with value v immediately after mark and returns e.
// If mark is not an element of l, the list is not modified.
// The mark must not be nil.
func (l *List) InsertAfter(v any, mark *Element) *Element {
	if mark.list != l {
		return nil
	}
	// see comment in List.Remove about initialization of l
	return l.insertValue(v, mark)
}

// MoveToFront moves element e to the front of list l.
// If e is not an element of l, the list is not modified.
// The element must not be nil.
func (l *List) MoveToFront(e *Element) {
	if e.list != l || l.root.next == e {
		return
	}
	// see comment in List.Remove about initialization of l
	l.move(e, &l.root)
}

// MoveToBack moves element e to the back of list l.
// If e is not an element of l, the list is not modified.
// The element must not be nil.
func (l *List) MoveToBack(e *Element) {
	if e.list != l || l.root.prev == e {
		return
	}
	// see comment in List.Remove about initialization of l
	l.move(e, l.root.prev)
}

// MoveBefore moves element e to its new position before mark.
// If e or mark is not an element of l, or e == mark, the list is not modified.
// The element and mark must not be nil.
func (l *List) MoveBefore(e, mark *Element) {
	if e.list != l || e == mark || mark.list != l {
		return
	}
	l.move(e, mark.prev)
}

// MoveAfter moves element e to its new position after mark.
// If e or mark is not an element of l, or e == mark, the list is not modified.
// The element and mark must not be nil.
func (l *List) MoveAfter(e, mark *Element) {
	if e.list != l || e == mark || mark.list != l {
		return
	}
	l.move(e, mark)
}

// PushBackList inserts a copy of another list at the back of list l.
// The lists l and other may be the same. They must not be nil.
func (l *List) PushBackList(other *List) {
	l.lazyInit()
	for i, e := other.Len(), other.Front(); i > 0; i, e = i-1, e.Next() {
		l.insertValue(e.Value, l.root.prev)
	}
}

// PushFrontList inserts a copy of another list at the front of list l.
// The lists l and other may be the same. They must not be nil.
func (l *List) PushFrontList(other *List) {
	l.lazyInit()
	for i, e := other.Len(), other.Back(); i > 0; i, e = i-1, e.Prev() {
		l.insertValue(e.Value, &l.root)
	}
}

```

go container/list

Bucket
===
```go
// Bucket 表示数据库中的键值对集合。
type Bucket struct {
    bucket     *bucket            // 内部 bucket 结构的引用
    tx         *Tx                // 关联的事务
    buckets    map[string]*Bucket // 子桶缓存
    page       *page              // 内联页面引用
    rootNode   *node              // 根页面的实体化节点
    nodes      map[pgid]*node     // 节点缓存

    // 设置节点分裂时填充节点的阈值。默认情况下，桶将填充到 50%，
    // 但如果你知道你的写入工作负载主要是追加式的，增加此百分比可能会有用。
    //
    // 这在事务之间是非持久的，因此必须在每个 Tx 中设置。
    FillPercent float64
}

```



BoltDb源码阅读（3） Bucket

中断是一种异步事件处理机制，用于提高系统的并发处理能力。在Linux中，中断的整个过程包括中断请求、中断处理和中断返回三个阶段。中断号是用来标识不同类型中断的数字或代码。





1. 中断请求阶段：
   - 硬件设备发出中断信号，通知处理器有一个中断事件发生。
   - 处理器接收到中断信号后，会立即向操作系统报告中断事件的发生。

2. 中断处理阶段：
   - 操作系统根据中断号找到对应的中断处理程序（中断服务例程，ISR）。
   - 中断处理程序是设备驱动程序的一部分，用于管理和处理特定设备的中断事件。
   - 中断处理程序运行在中断上下文中，它具有较高的优先级，可以打断正在执行的进程。
   - 中断处理程序执行特定的操作，例如读取设备数据、更新设备状态等。

3. 中断返回阶段：
   - 中断处理程序执行完毕后，操作系统会将控制权返回给被打断的进程或任务。
   - 被打断的进程或任务从中断发生时的状态继续执行。

在Linux中，每个中断都有一个唯一的中断号来标识不同类型的中断。中断号通常被称为中断请求（IRQ）线，每个IRQ线都与一个特定的设备或事件相关联。



---
Learn more:
1. [Linux内核学习笔记之中断和中断处理 | 普通人](https://hjk.life/posts/linux-kernel-interrupt/)
2. [Linux中断和中断处理程序 - 明明1109 - 博客园](https://www.cnblogs.com/fortunely/p/15856752.html)
3. [Linux内核21-Linux内核的中断处理过程 - 图珀洛的博客 | TUPELO Blog](http://tupelo-shen.github.io/2020/03/25/Linux%E5%86%85%E6%A0%B821-Linux%E5%86%85%E6%A0%B8%E7%9A%84%E4%B8%AD%E6%96%AD%E5%A4%84%E7%90%86%E8%BF%87%E7%A8%8B/)

1. [Linux内核之中断机制_中断是一种异步事件处理机制-CSDN博客](https://blog.csdn.net/Micky_Yang/article/details/104357903)
2. [Linux 内核中断内幕 - 随风飘落的雨滴 - 博客园](https://www.cnblogs.com/dirt2/p/5616217.html)
3. [深入理解Linux内核中断及其特性(更新)](http://junqilee.com/linux/%E6%B7%B1%E5%85%A5%E7%90%86%E8%A7%A3linux%E5%86%85%E6%A0%B8%E4%B8%AD%E6%96%AD%E5%8F%8A%E5%85%B6%E7%89%B9%E6%80%A7-%E6%9B%B4%E6%96%B0/)

中断处理

DB对象
===
```go
// DB 表示一个在磁盘上持久化存储的桶集合。
// 所有数据访问都通过事务进行，可以通过 DB 获得事务。
// 如果在调用 Open() 之前访问，DB 上的所有函数将返回 ErrDatabaseNotOpen。
type DB struct {
	StrictMode   bool   // 启用严格模式时，数据库将在每次提交后执行 Check()。如果数据库处于不一致状态，则引发 panic。该标志对性能有很大的影响，因此仅应用于调试目的。
	NoSync       bool   // 设置 NoSync 标志将导致数据库在每次提交后跳过 fsync() 调用。在将数据批量加载到数据库中并且可以在系统故障或数据库损坏时重新启动批量加载时，可以使用此标志。请勿在正常使用中设置此标志。
	NoGrowSync   bool   // 当为 true 时，当扩展数据库时跳过 truncate 调用。仅在非 ext3/ext4 系统上设置此标志是安全的。跳过截断避免了硬盘空间的预分配，并且在重新映射时避免了 truncate() 和 fsync() 系统调用。
	MmapFlags    int    // 如果要快速读取整个数据库，则可以将 MmapFlag 设置为 syscall.MAP_POPULATE，用于 Linux 2.6.23+ 的顺序读取预读。
	MaxBatchSize int    // MaxBatchSize 是批处理的最大大小。默认值从 Open 中的 DefaultMaxBatchSize 复制。如果 <= 0，则禁用批处理。在调用 Batch 时请勿并发更改。
	MaxBatchDelay time.Duration // MaxBatchDelay 是批处理开始前的最大延迟。默认值从 Open 中的 DefaultMaxBatchDelay 复制。如果 <= 0，则 effectively 禁用批处理。在调用 Batch 时请勿并发更改。
	AllocSize    int    // AllocSize 是数据库需要创建新页面时分配的空间量。这样做是为了分摊增长数据文件时 truncate() 和 fsync() 的成本。
	path         string // 数据库文件路径
	file         *os.File
	lockfile     *os.File // 仅 Windows 平台需要
	dataref      []byte   // mmap'ed readonly，写操作会引发 SEGV
	data         *[maxMapSize]byte
	datasz       int   // 数据大小
	filesz       int   // 当前磁盘上的文件大小
	meta0        *meta // meta 数据页
	meta1        *meta // meta 数据页
	pageSize     int   // 页面大小
	opened       bool  // 是否已打开数据库
	rwtx         *Tx   // 当前读写事务
	txs          []*Tx // 事务列表
	freelist     *freelist // 空闲列表
	stats        Stats     // 统计信息
	pagePool     sync.Pool
	batchMu      sync.Mutex // 批处理锁
	batch        *batch
	rwlock       sync.Mutex   // 仅允许一个写入者
	metalock     sync.Mutex   // 保护 meta 页访问
	mmaplock     sync.RWMutex // 保护在重新映射期间的 mmap 访问
	statlock     sync.RWMutex // 保护统计信息访问

	ops struct {
		writeAt func(b []byte, off int64) (n int, err error)
	}

	// 只读模式。
	// 当为 true 时，Update() 和 Begin(true) 立即返回 ErrDatabaseReadOnly。
	readOnly bool
}

```
Open
===
```go
// Options 表示在打开数据库时可以设置的选项。
type Options struct {
    // Timeout 是获取文件锁时等待的时间。
    // 当设置为零时，将无限等待。此选项仅在 Darwin 和 Linux 上可用。
    Timeout time.Duration

    // 在内存映射文件之前设置 DB.NoGrowSync 标志。
    NoGrowSync bool

    // 以只读模式打开数据库。使用 flock(..., LOCK_SH |LOCK_NB) 来获取共享锁（UNIX）。
    ReadOnly bool

    // 在内存映射文件之前设置 DB.MmapFlags 标志。
    MmapFlags int

    // InitialMmapSize 是数据库的初始 mmap 大小（以字节为单位）。
    // 如果 InitialMmapSize 大到足以容纳数据库的 mmap 大小，那么读事务不会阻塞写事务。
    // 如果 <= 0，则初始映射大小为 0。
    // 如果 initialMmapSize 小于先前的数据库大小，则不起作用。
    InitialMmapSize int
}

// Open 创建并打开指定路径的数据库。
// 如果文件不存在，则将自动创建。
// 如果未提供选项（options为nil），则 Bolt 将使用默认选项打开数据库。
func Open(path string, mode os.FileMode, options *Options) (*DB, error) {
    // 创建一个数据库实例，并设置 opened 为 true，表示数据库已打开
    var db = &DB{opened: true}

    // 如果未提供选项，则使用默认选项
    if options == nil {
        options = DefaultOptions
    }
    db.NoGrowSync = options.NoGrowSync
    db.MmapFlags = options.MmapFlags

    // 设置后续数据库操作的默认值
    db.MaxBatchSize = DefaultMaxBatchSize
    db.MaxBatchDelay = DefaultMaxBatchDelay
    db.AllocSize = DefaultAllocSize

    // 根据只读选项设置文件打开标志
    flag := os.O_RDWR
    if options.ReadOnly {
        flag = os.O_RDONLY
        db.readOnly = true
    }

    // 打开数据文件并为元数据写入创建单独的同步处理程序
    db.path = path
    var err error
    if db.file, err = os.OpenFile(db.path, flag|os.O_CREATE, mode); err != nil {
        _ = db.close()
        return nil, err
    }

    // 锁定文件，以便使用 Bolt 的其他进程在读写模式下不能同时使用数据库
    // 这样做是为了防止两个进程分别写入 meta 页面和 free 页面，导致数据库损坏
    // 如果 !options.ReadOnly，则数据库文件以独占锁定（只有一个进程可以获得锁）
    // 否则（options.ReadOnly 已设置），使用共享锁定（多个进程可以同时持有锁）
    if err := flock(db, mode, !db.readOnly, options.Timeout); err != nil {
        _ = db.close()
        return nil, err
    }

    // 默认值用于测试钩子
    db.ops.writeAt = db.file.WriteAt

    // 如果数据库文件不存在，则进行初始化
    if info, err := db.file.Stat(); err != nil {
        return nil, err
    } else if info.Size() == 0 {
        // 初始化具有 meta 页面的新文件
        if err := db.init(); err != nil {
            return nil, err
        }
    } else {
        // 读取第一个 meta 页面以确定页面大小
        var buf [0x1000]byte
        if _, err := db.file.ReadAt(buf[:], 0); err == nil {
            m := db.pageInBuffer(buf[:], 0).meta()
            if err := m.validate(); err != nil {
                // 如果无法读取页面大小，我们可以假设它与 OS 相同
                // 因为这是首次选择页面大小的方式
                // 如果第一个页面无效且此 OS 使用与创建数据库时不同的页面大小，则无法访问数据库
                db.pageSize = os.Getpagesize()
            } else {
                db.pageSize = int(m.pageSize)
            }
        }
    }

    // 初始化页面池
    db.pagePool = sync.Pool{
        New: func() interface{} {
            return make([]byte, db.pageSize)
        },
    }

    // 内存映射数据文件
    if err := db.mmap(options.InitialMmapSize); err != nil {
        _ = db.close()
        return nil, err
    }

    // 读取空闲列表
    db.freelist = newFreelist()
    db.freelist.read(db.page(db.meta().freelist))

    // 标记数据库已打开并返回
    return db, nil
}

```
mmap
===



1. **mmap**
   ```go
   // mmap 打开底层的内存映射文件并初始化 meta 引用。
   // minsz 是新 mmap 可以拥有的最小大小。
   func (db *DB) mmap(minsz int) error {
       db.mmaplock.Lock()
       defer db.mmaplock.Unlock()

       info, err := db.file.Stat()
       if err != nil {
           return fmt.Errorf("mmap stat error: %s", err)
       } else if int(info.Size()) < db.pageSize*2 {
           return fmt.Errorf("file size too small")
       }

       // 确保大小至少是最小大小。
       var size = int(info.Size())
       if size < minsz {
           size = minsz
       }
       size, err = db.mmapSize(size)
       if err != nil {
           return err
       }

       // 在继续之前解除所有 mmap 引用。
       if db.rwtx != nil {
           db.rwtx.root.dereference()
       }

       // 在继续之前取消映射现有数据。
       if err := db.munmap(); err != nil {
           return err
       }

       // 将数据文件作为字节切片进行内存映射。
       if err := mmap(db, size); err != nil {
           return err
       }

       // 保存对 meta 页面的引用。
       db.meta0 = db.page(0).meta()
       db.meta1 = db.page(1).meta()

       // 验证 meta 页面。只有在两个 meta 页面都无法验证时才返回错误，
       // 因为 meta0 无法验证意味着它没有被正确保存，但我们可以使用 meta1 进行恢复。反之亦然。
       err0 := db.meta0.validate()
       err1 := db.meta1.validate()
       if err0 != nil && err1 != nil {
           return err0
       }

       return nil
   }
   ```

   - `mmap` 函数用于打开底层的内存映射文件，并初始化 `meta` 引用。
   - `minsz` 是新 mmap 可以拥有的最小大小。
   - 函数首先获取数据库文件的信息，确保文件大小至少是两个页面大小。
   - 然后确定实际的 mmap 大小，并进行内存映射。
   - 函数最后保存对 `meta` 页面的引用，并验证这些页面的有效性。

2. **munmap**
   ```go
   // munmap 从内存中取消映射数据文件。
   func (db *DB) munmap() error {
       if err := munmap(db); err != nil {
           return fmt.Errorf("unmap error: " + err.Error())
       }
       return nil
   }
   ```

   - `munmap` 函数用于从内存中取消映射数据文件。
   - 调用 `munmap` 函数并返回可能的错误信息。

3. **mmapSize**
   ```go
   // mmapSize 根据当前数据库的大小确定 mmap 的适当大小。
   // 最小大小为32KB，每次翻倍直到达到1GB。
   // 如果新的 mmap 大小大于允许的最大值，则返回错误。
   func (db *DB) mmapSize(size int) (int, error) {
       // 从32KB开始翻倍直到1GB。
       for i := uint(15); i <= 30; i++ {
           if size <= 1<<i {
               return 1 << i, nil
           }
       }

       // 验证请求的大小不超过允许的最大值。
       if size > maxMapSize {
           return 0, fmt.Errorf("mmap too large")
       }

       // 如果大于1GB，则每次增加1GB。
       sz := int64(size)
       if remainder := sz % int64(maxMmapStep); remainder > 0 {
           sz += int64(maxMmapStep) - remainder
       }

       // 确保 mmap 大小是页面大小的倍数。
       // 这应该总是正确的，因为我们以MB为单位递增。
       pageSize := int64(db.pageSize)
       if (sz % pageSize) != 0 {
           sz = ((sz / pageSize) + 1) * pageSize
       }

       // 如果超过最大大小，则仅增长到最大大小。
       if sz > maxMapSize {
           sz = maxMapSize
       }

       return int(sz), nil
   }
   ```

   - `mmapSize` 函数根据当前数据库的大小确定 mmap 的适当大小。
   - 最小大小为32KB，每次翻倍直到达到1GB。
   - 如果新的 mmap 大小大于允许的最大值，则返回错误。
   
系统调用
===


1. **mmap**
   ```go
   // mmap 将数据库的数据文件映射到内存中。
   func mmap(db *DB, sz int) error {
       // 将数据文件映射到内存。
       b, err := syscall.Mmap(int(db.file.Fd()), 0, sz, syscall.PROT_READ, syscall.MAP_SHARED|db.MmapFlags)
       if err != nil {
           return err
       }

       // 告知内核 mmap 是随机访问的。
       if err := madvise(b, syscall.MADV_RANDOM); err != nil {
           return fmt.Errorf("madvise: %s", err)
       }

       // 保存原始的字节切片并转换为字节数组指针。
       db.dataref = b
       db.data = (*[maxMapSize]byte)(unsafe.Pointer(&b[0]))
       db.datasz = sz
       return nil
   }
   ```
   - `mmap` 函数使用 `syscall.Mmap` 将数据库文件映射到内存中。
   - `db.file.Fd()` 返回数据库文件的文件描述符。
   - 映射的区域从文件的偏移量 0 处开始，大小为 `sz` 字节。
   - `syscall.PROT_READ` 表示映射区域可读。
   - `syscall.MAP_SHARED` 表示对映射区域的写入会反映到文件中，并且此映射区域可能被其他映射它的进程看到。
   - `db.MmapFlags` 包含其他 mmap 选项。
   - `madvise` 用于告知内核，映射是随机访问的，这可以提高性能。
   - 函数保存了原始的字节切片 `b`，并将其转换为一个指向字节数组的指针 `db.data`，以及记录了映射的大小 `db.datasz`。

2. **munmap**
   ```go
   // munmap 从内存中取消映射数据文件。
   func munmap(db *DB) error {
       // 如果没有映射数据，则忽略取消映射。
       if db.dataref == nil {
           return nil
       }

       // 使用原始的字节切片取消映射。
       err := syscall.Munmap(db.dataref)
       db.dataref = nil
       db.data = nil
       db.datasz = 0
       return err
   }
   ```
   - `munmap` 函数用于从内存中取消映射数据文件。
   - 如果没有映射数据，则直接返回。
   - 调用 `syscall.Munmap` 函数取消映射，并清空相应的字段。

3. **madvise**
   ```go
   // madvise 通知内核有关于内存映射的信息。
   // 由于该函数在 darwin 上不可用，因此从 stdlib 复制而来。
   func madvise(b []byte, advice int) (err error) {
       _, _, e1 := syscall.Syscall(syscall.SYS_MADVISE, uintptr(unsafe.Pointer(&b[0])), uintptr(len(b)), uintptr(advice))
       if e1 != 0 {
           err = e1
       }
       return
   }
   ```
   - `madvise` 函数通知内核有关于内存映射的信息。
   - 由于在 Darwin 上 `madvise` 不可用，因此从标准库复制了该函数。

4. **flock**
   ```go
   // flock 在文件描述符上获取一个咨询性的锁。
   func flock(db *DB, mode os.FileMode, exclusive bool, timeout time.Duration) error {
       var t time.Time
       for {
           // 如果超出超时时间，则返回错误。
           // 这只能在我们尝试过一次 flock 之后发生。
           if t.IsZero() {
               t = time.Now()
           } else if timeout > 0 && time.Since(t) > timeout {
               return ErrTimeout
           }
           flag := syscall.LOCK_SH
           if exclusive {
               flag = syscall.LOCK_EX
           }

           // 否则尝试获取独占锁。
           err := syscall.Flock(int(db.file.Fd()), flag|syscall.LOCK_NB)
           if err == nil {
               return nil
           } else if err != syscall.EWOULDBLOCK {
               return err
           }

           // 等待一会儿然后再次尝试。
           time.Sleep(50 * time.Millisecond)
       }
   }
   ```
   - `flock` 函数在文件描述符上获取一个咨询性的锁。
   - `mode` 表示锁的模式，`exclusive` 为 `true` 表示独占锁，为 `false` 表示共享锁。
   - `timeout` 表示等待锁的最长时间，如果超过此时间还未获取到锁，则返回超时错误。
   - 函数使用 `syscall.Flock` 尝试获取锁，如果成功则返回 `nil`。
   - 如果返回的错误为 `syscall.EWOULDBLOCK` 表示当前无法获得锁，等待一段时间后再次尝试。

5. **funlock**
   ```go
   // funlock 释放文件描述符上的咨询性锁。
   func funlock(db *DB) error {
       return syscall.Flock(int(db.file.Fd()), syscall.LOCK_UN)
   }
   ```
   - `funlock
` 函数释放文件描述符上的咨询性锁，使用 `syscall.Flock` 并指定 `syscall.LOCK_UN` 表示释放锁。


Update View
===
```go
// Update 在读写托管事务的上下文中执行一个函数。
// 如果函数没有返回错误，则提交事务。
// 如果函数返回错误，则整个事务将被回滚。
// Update() 方法返回函数中的错误或提交时的错误。
//
// 在函数中尝试手动提交或回滚将引发 panic。
func (db *DB) Update(fn func(*Tx) error) error {
    // 开始一个读写事务。
    t, err := db.Begin(true)
    if err != nil {
        return err
    }

    // 确保在发生 panic 时事务回滚。
    defer func() {
        if t.db != nil {
            t.rollback()
        }
    }()

    // 将事务标记为托管，以便内部函数不能手动提交。
    t.managed = true

    // 如果函数返回错误，则回滚并返回错误。
    err = fn(t)
    t.managed = false
    if err != nil {
        _ = t.Rollback()
        return err
    }

    // 提交事务。
    return t.Commit()
}


// View 在托管的只读事务上下文中执行一个函数。
// 从函数返回的任何错误都将从 View() 方法中返回。
//
// 在函数中尝试手动回滚将引发 panic。
func (db *DB) View(fn func(*Tx) error) error {
    // 开始一个只读事务。
    t, err := db.Begin(false)
    if err != nil {
        return err
    }

    // 确保在发生 panic 时事务回滚。
    defer func() {
        if t.db != nil {
            t.rollback()
        }
    }()

    // 将事务标记为托管，以便内部函数不能手动回滚。
    t.managed = true

    // 如果函数返回错误，则传递该错误。
    err = fn(t)
    t.managed = false
    if err != nil {
        _ = t.Rollback()
        return err
    }

    // 手动回滚事务，因为只读事务不需要提交。
    if err := t.Rollback(); err != nil {
        return err
    }

    return nil
}

```


mate
===
```go
// meta 获取当前的 meta 页引用。
func (db *DB) meta() *meta {
    // 我们必须返回具有最高 txid 且未失败验证的 meta 页引用。
    // 否则，在实际上数据库处于一致状态时，可能会导致错误。
    // metaA 是 txid 较高的 meta 页。
    metaA := db.meta0
    metaB := db.meta1
    if db.meta1.txid > db.meta0.txid {
        metaA = db.meta1
        metaB = db.meta0
    }

    // 如果 metaA 有效，则使用较高的 meta 页。否则，如果 metaB 有效，则回退到上一个。
    if err := metaA.validate(); err == nil {
        return metaA
    } else if err := metaB.validate(); err == nil {
        return metaB
    }

    // 不应该到达这里，因为 meta1 和 meta0 在 mmap() 时已经验证过，并且我们在每次写操作时都执行 fsync()。
    panic("bolt.DB.meta(): invalid meta pages")
}

```

BoltDb源码阅读（2） DB

bolt是个简单的kv嵌入式数据库，同sqlite是一样的定位，boltdb开启一个数据库的时候，一样也是新建一个.db文件，文件里的数据按page来组织，一个数据库又分为bucket来组织数据（类似于表）。




![image.png](/static/img/8a06191ee7901b16f9165e1997d5c452.image.webp)

- bolt使用B+树来索引数据，一个bucket对应一棵树
- bolt使用mmap来直接映射db文件
- bolt支持subbucket

Page结构
===
bolt按页来读取和写入数据，一页大小为4k,一个页结构分为**页头和真实数据**,所有的数据在磁盘上都是按照页(page)来存储的
```go
type pgid uint64
type page struct {
    // 页id 8字节
    id pgid
    // flags：页类型，可以是分支，叶子节点，元信息，空闲列表  2字节，该值的取值详细参见下面描述
    flags uint16
    // 个数 2字节，统计叶子节点、非叶子节点、空闲列表页的个数
    count uint16
    // 4字节，数据是否有溢出，主要在空闲列表上有用
    overflow uint32
    // 真实的数据
    ptr uintptr
}

```

![image.png](/static/img/90e5b521d5e9be2f4d7ea5973201e687.image.webp)

Page Type
===
bolt将页分为以下类型组织起来，用常量来描述

- 分支节点页	branchPageFlag	0x01	存储索引信息(页号、元素key值)
- 叶子节点页	leafPageFlag	0x02	存储数据信息(页号、插入的key值、插入的value值)
- 元数据页	metaPageFlag	0x04	存储数据库的元信息，例如空闲列表页id、放置桶的根页等
- 空闲列表页	freelistPageFlag	0x10	存储哪些页是空闲页，可以用来后续分配空间时，优先考虑分配



```go
// 页头的大小：16字节
const pageHeaderSize = int(unsafe.Offsetof(((*page)(nil)).ptr))
const minKeysPerPage = 2
//分支节点页中每个元素所占的大小
const branchPageElementSize = int(unsafe.Sizeof(branchPageElement{}))
//叶子节点页中每个元素所占的大小
const leafPageElementSize = int(unsafe.Sizeof(leafPageElement{}))
const (
    branchPageFlag   = 0x01 //分支节点页类型
    leafPageFlag     = 0x02 //叶子节点页类型
    metaPageFlag     = 0x04 //元数据页类型
    freelistPageFlag = 0x10 //空闲列表页类型
)

// typ returns a human readable page type string used for debugging.
func (p *page) typ() string {
    if (p.flags & branchPageFlag) != 0 {
        return "branch"
    } else if (p.flags & leafPageFlag) != 0 {
        return "leaf"
    } else if (p.flags & metaPageFlag) != 0 {
        return "meta"
    } else if (p.flags & freelistPageFlag) != 0 {
        return "freelist"
    }
    return fmt.Sprintf("unknown<%02x>", p.flags)
}
```
所有的page都有type方法
### mate page

```go
// meta returns a pointer to the metadata section of the page.
func (p *page) meta() *meta {
    // 将p.ptr转为meta信息
    return (*meta)(unsafe.Pointer(&p.ptr))
}

type meta struct {
    magic    uint32 //魔数
    version  uint32 //版本
    pageSize uint32 //page页的大小，该值和操作系统默认的页大小保持一致
    flags    uint32 //保留值，目前貌似还没用到
    root     bucket //所有小柜子bucket的根
    freelist pgid //空闲列表页的id
    pgid     pgid //元数据页的id
    txid     txid //最大的事务id
    checksum uint64 //用作校验的校验和
}

```
元数据的组织方式

![image.png](/static/img/02b2a8ba50f813c7a88cac45bc15da85.image.webp)

### freelist
```go
// freelist represents a list of all pages that are available for allocation.
// It also tracks pages that have been freed but are still in use by open transactions.
type freelist struct {
    // 已经可以被分配的空闲页
    ids     []pgid          // all free and available free page ids.
    // 将来很快能被释放的空闲页，部分事务可能在读或者写
    pending map[txid][]pgid // mapping of soon-to-be free page ids by tx.
    cache   map[pgid]bool   // fast lookup of all free and pending page ids.
}
// newFreelist returns an empty, initialized freelist.
func newFreelist() *freelist {
    return &freelist{
        pending: make(map[txid][]pgid),
        cache:   make(map[pgid]bool),
    }
}
```

![image.png](/static/img/a55bde389fd04283c54108450f0cf6a9.image.webp)

将空闲列表转换成页信息，写到磁盘中，此处需要注意一个问题，页头中的count字段是一个uint16，占两个字节，其最大可以表示2^16 即65536个数字，当空闲页的个数超过65535时时，需要将p.ptr中的第一个字节用来存储其空闲页的个数，同时将p.count设置为0xFFFF。否则不超过的情况下，直接用count来表示其空闲页的个数

---
**freelist->page**
```go
// write writes the page ids onto a freelist page. All free and pending ids are
// saved to disk since in the event of a program crash, all pending ids will
// become free.
//将 freelist信息写入到p中
func (f *freelist) write(p *page) error {
    // Combine the old free pgids and pgids waiting on an open transaction.
    // Update the header flag.
    // 设置页头中的页类型标识
    p.flags |= freelistPageFlag
    // The page.count can only hold up to 64k elements so if we overflow that
    // number then we handle it by putting the size in the first element.
    lenids := f.count()
    if lenids == 0 {
        p.count = uint16(lenids)
    } else if lenids < 0xFFFF {
        p.count = uint16(lenids)
        // 拷贝到page的ptr中
        f.copyall(((*[maxAllocSize]pgid)(unsafe.Pointer(&p.ptr)))[:])
    } else {
        // 有溢出的情况下，后面第一个元素放置其长度，然后再存放所有的pgid列表
        p.count = 0xFFFF
        ((*[maxAllocSize]pgid)(unsafe.Pointer(&p.ptr)))[0] = pgid(lenids)
        // 从第一个元素位置拷贝
        f.copyall(((*[maxAllocSize]pgid)(unsafe.Pointer(&p.ptr)))[1:])
    }
    return nil
}
// copyall copies into dst a list of all free ids and all pending ids in one sorted list.
// f.count returns the minimum length required for dst.
func (f *freelist) copyall(dst []pgid) {
    // 首先把pending状态的页放到一个数组中，并使其有序
    m := make(pgids, 0, f.pending_count())
    for _, list := range f.pending {
        m = append(m, list...)
    }
    sort.Sort(m)
    // 合并两个有序的列表，最后结果输出到dst中
    mergepgids(dst, f.ids, m)
}
// mergepgids copies the sorted union of a and b into dst.
// If dst is too small, it panics.
// 将a和b按照有序合并成到dst中，a和b有序
func mergepgids(dst, a, b pgids) {
    if len(dst) < len(a)+len(b) {
        panic(fmt.Errorf("mergepgids bad len %d < %d + %d", len(dst), len(a), len(b)))
    }
    // Copy in the opposite slice if one is nil.
    if len(a) == 0 {
        copy(dst, b)
        return
    }
    if len(b) == 0 {
        copy(dst, a)
        return
    }
    // Merged will hold all elements from both lists.
    merged := dst[:0]
    // Assign lead to the slice with a lower starting value, follow to the higher value.
    lead, follow := a, b
    if b[0] < a[0] {
        lead, follow = b, a
    }
    // Continue while there are elements in the lead.
    for len(lead) > 0 {
        // Merge largest prefix of lead that is ahead of follow[0].
        n := sort.Search(len(lead), func(i int) bool { return lead[i] > follow[0] })
        merged = append(merged, lead[:n]...)
        if n >= len(lead) {
            break
        }
        // Swap lead and follow.
        lead, follow = follow, lead[n:]
    }
    // Append what's left in follow.
    _ = append(merged, follow...)
}
```
**allocate**
```go
// allocate returns the starting page id of a contiguous list of pages of a given size.
// If a contiguous block cannot be found then 0 is returned.
// [5,6,7,13,14,15,16,18,19,20,31,32]
// 开始分配一段连续的n个页。其中返回值为初始的页id。如果无法分配，则返回0即可
func (f *freelist) allocate(n int) pgid {
    if len(f.ids) == 0 {
        return 0
    }
    var initial, previd pgid
    for i, id := range f.ids {
        if id <= 1 {
            panic(fmt.Sprintf("invalid page allocation: %d", id))
        }
        // Reset initial page if this is not contiguous.
        // id-previd != 1 来判断是否连续
        if previd == 0 || id-previd != 1 {
            // 第一次不连续时记录一下第一个位置
            initial = id
        }
        // If we found a contiguous block then remove it and return it.
        // 找到了连续的块，然后将其返回即可
        if (id-initial)+1 == pgid(n) {
            // If we're allocating off the beginning then take the fast path
            // and just adjust the existing slice. This will use extra memory
            // temporarily but the append() in free() will realloc the slice
            // as is necessary.
            if (i + 1) == n {
                // 找到的是前n个连续的空间
                f.ids = f.ids[i+1:]
            } else {
                copy(f.ids[i-n+1:], f.ids[i+1:])
                f.ids = f.ids[:len(f.ids)-n]
            }
            // Remove from the free cache.
            // 同时更新缓存
            for i := pgid(0); i < pgid(n); i++ {
                delete(f.cache, initial+i)
            }
            return initial
        }
        previd = id
    }
    return 0
}
```