git: 以 hash 值作 key 的 file system
current 变更文件信息: 更新(insert/replace)到 git track 的 cache&index 文件中
|
".dircache/index" = .dircache/index.lock" |
| |
| |
cache / index 文件 = header + 变更文件信息(git track) memmory blocks
|\
| 指向
|
变更文件信息 (struct 的) pointer array 各 ptrs
struct cache_entry **active_cache |\
elem: 变更文件信息 | 赋值
- -name: filename |
| sha1[20] read_cache()
| |
| | `以 hash 值作 key 的 file system`
| |
| blob obj: 名字 40 个 hex: 内部存储 sha1[20]
| /| |\
| 压缩 | | 解压
| |/ |
| blob original obj - -> content(git track)
| /
| /
|- - - - - current content(可能已改)
[1] 更新到 blob original obj -> 压缩到 blob obj
[2] 与 git track 的 content 比较
1 Git 系统 设计: 8 个 .o/.c
cache.h
1. init-db.c
$ ./init-db
main()
建 sha1 dir
默认 dir: ".dircache/objects"
在 其中 建 名为 00-ff 的 256 个 目录
2. read-cache.c: 没 main() => func_name 在 symbol table 中
sha1 值 2 种格式:
输入格式 : 40 个 hex 的 字符串 /
内部(存储/计算)格式 : 20 个 Bytes 的 unsigned char array / char []: unsigned char *
每次调 read-cache.o -> 4 大 全局变量 初始化 为 NULL 或 0
(1) int get_sha1_hex(char *hex, unsigned char *sha1)
`sha1 值` 格式转换: 输入格式 -> 内部形式
(2) char * sha1_to_hex(unsigned char *sha1)
`sha1 值` 格式转换: 内部形式 -> 输入格式
(3) char *sha1_file_name(unsigned char *sha1)
由 sha1 值 (内部格式) 解析 sha1 object filename = dircache/objects/../..."
(4) int read_cache(void)
index 文件 mmap 映射到 进程虚拟内存
`变更文件信息 pointer array` 各 `pointer` 指向 `虚拟内存中 各 变更文件信息 memory block`
(5) int write_sha1_file(char *buf,unsigned len)
[1] zlib 压缩 sha1 original object(的 malloc 内存 buf)
[2] 将压缩后所得 sha1 object write 到 sha1 object 文件
write_sha1_buffer(sha1, compressed, size)
filename = sha1_file_name(sha1)
fd = open
write(fd, buf, size) // buf == compressed, write 到 sha1 object 文件
(6) void * read_sha1_file(unsigned char *sha1,
char *type,
unsigned long *size)
[1] sha1_file_name(sha1)
sha1 值 -> sha1 object filename
[2] mmap
[3] zlib 解压 出 sha1 original object
1] header 中 "type/size" 读 (sscanf) 到 type/size 所指 内存
2] 有效 content 放到 malloc 堆内存 -> ptr 返回
3. update-cache.c
$ ./update-cache <file>
(1) read_cache()
index 文件 mmap
变更文件信息 pointer array 各 ptrs 指向 `虚拟内存中 各 变更文件信息 的 memory block`
(2) 打开 index.lock
以 O_CREAT | O_EXCL 方式
保证 `同时只允许 1 个 进程` 将 `变更文件信息` 写入 index.lock
(3) `遍历` update-cache.o 入参中 各 `变更文件 path`
1) add_file_to_cache(path) -> 删 index.lock
2) write_cache(newfd, active_cache, active_nr)
actice_cache 所指 `虚拟内存 和 新堆内存` 中 `变更文件信息` write 到 index.lock
3) rename(".dircache/index.lock", ".dircache/index")
index.lock 重命名为 index
static int add_file_to_cache(char *path)
(1) remove_file_from_cache(path)
若 同时存在 另一进程 正在 read_cache(), remove ...
(2) cache_entry_size(namelen)
(3) malloc `变更文件信息 新堆内存 ce: 放 blob original object`
\
(4) index_fd(...)
1) fill header + `变更文件 content` mmap = blob original object
2) 压缩 -> blob object
3) write 到 sha1 object 文件: write_sha1_buffer( ... )
(5) add_cache_entry(ce)
pos = cache_name_pos(ce->name, ce->namelen)
二分法
由 pos 判 existing mathch ?
是: prt replace 到 变更文件信息 pointer array 中 合适 position
否: ptr insert
4. cat-file.c
$ ./cat-file <sha1>
(1) get_sha1_hex(argv[1], sha1)
sha1 由输入格式 转为 内部格式
(2) read_sha1_file(sha1, type, &size)
sha1 -> sha1 object -> zlib 解压 -> sha1 original object
(3) mkstemp(template)
建 (唯一)临时文件
(4) write(fd, buf, size)
输出 type
write sha1 original object 有效 content 到 (唯一)临时文件
5. show-diff.c
$ ./show-diff
(1) read_cache()
(2) 遍历 cache 中 变更文件信息
1) stat(ce->name, &st): 将 `current 变更文件 (可能已变) state` copy 到 &st 所指内存
2) match_stat(ce, &st): 比较 `current 变更文件 state` 与 `cache 中 相应的 文件 state`, 匹配 查找 是哪种 change
3) unchanged: print ok -> continue
4) changed
new = read_sha1_file(ce->sha1, type, &size)
show_differences(ce, &st, new, size)
f = popen("diff -u -<ce->name>", w)
fwrite(old_contents == new, old_size, 1, f)
2 数据结构
1. directory cache: index 文件
(1) header
struct cache_header {
unsigned int signature;
unsigned int version;
unsigned int entries;
unsigned char sha1[20]; // totalSha1 值
};
(2) (单个) 变更文件信息 struct
struct cache_entry {
struct cache_time ctime; // 文件 state 改变时间
struct cache_time mtime; // 文件 content 最后修改时间
unsigned int st_dev; // 设备号
unsigned int st_ino; // inode 节点号
unsigned int st_mode; // 文件模式
unsigned int st_uid; // 文件 所有者 (user) Id
unsigned int st_gid; // 文件 所有者所在 group Id
unsigned int st_size; // 文件 Byte 数
unsigned char sha1[20];
unsigned short namelen; //
unsigned char name[0]; /* 0长数组 */
};
struct cache_time { // 8Byte
unsigned int sec;
unsigned int nsec;
};
2. 3种对象
blob
\
tree - original object, 又称 `objects original 对象` : struct
/
commit |
|
|
压缩
|
|
blob |
\
tree — object, 又称 `objects 对象 / sha1 object` : 二进制流
/
commit
|
| 从 `压缩 输出 buf` 写到
|
objects 对象 ( sha1 object ) 文件: filename == 40 个 hex/hash 值
3. cache: 变更文件信息 (struct 的) pointer array 中各 ptrs 所指 memory blocks (进程虚拟 + 堆)
3 全局变量
sha1_file_directory
active_cache
active_nr
active_alloc
均是 试探性定义, 不用 extern == 用 extern, 表现为 声明: cache.h
1. struct cache_entry **active_cache
含义:
变更文件信息 (struct 的) pointer array 的 指针
各 pointer 指向 index 文件 mmap 出的 虚拟内存空间 中 各 变更文件信息 memory block —— 称为 cache
note: 二级指针 + 一级指针 个数 n <=> 一级 指针数组
——————————————————————————————————————————————————————————————
| pointer array | | index 文件 mmap 的 虚拟内存 |
——————————————————————————————————————————————————————————————
| ptr1: cache_entry * | -> | 变更文件1信息 struct |
| | | |
| ptr2 | -> | 变更文件1信息 struct |
| | | |
| ... | ... | ... |
—————————————————————————————————————————————————————————————
初始化
read-cache.c 每次调用时 初始化为 NULL
赋值
(1) read-cache() 中 calloc 为 pointer array 分配内存 时 (calloc)
(2) add_cache_entry(struct cache_entry *ce) 中,
在 pointer array 所指 memory blocks 中 existing match,
且 pointer array 满载 时 (realloc)
各 pointer 赋值: 指向 所管理的 memory block
(1) read-cache() 中 index 文件 mmap 后
(2) add_cache_entry(struct cache_entry *ce) 中,
在 pointer array 所指 memory blocks 中 查找
existing match 时, replace (赋值)
else, insert (赋值)
2. unsigned int active_nr
含义:
index 文件中 `变更文件个数` = entries
赋值: read-cache.c
read_cache()
active_nr = hdr->entries; // struct cache_header *hdr;
3. unsigned int active_alloc
含义:
实际分配的 变更文件信息 指针数组 的 指针元素数
4. sha1_file_directory
(1) 是 sha1/object 文件目录
(2) 可默认 可通过环境变量设置
设为 默认值 : ".dircache/objects" == 宏 DEFAULT_DB_ENVIRONMENT
通过环境变量设置: getenv(宏 DB_ENVIRONMENT == "SHA1_FILE_DIRECTORY" )
(3) 代码结构
定义:
const char *sha1_file_directory = NULL;
试探性定义 / 声明: cache.h
const char *sha1_file_directory;
使用: read-tree.c
#include <cache.h>
sha1_file_directory = getenv(DB_ENVIRONMENT) ? : DEFAULT_DB_ENVIRONMENT;
4 Linux
1. int open(const char* pathname, int oflag, ...)
#include <fcntl.h>
pathname 可以是 绝对 也可以是 相对路径
文件打开方式
O_RDONLY 只读
O_WRONLY 只写
O_RDWR 读写
O_CREAT 文件不存在时创建
O_EXCL 若同时指定了 O_CREAT, 而 文件已存在, 则出错
2. int unlink(const char* pathname)
删除 pathname 指定的 文件
3. mmap
void *mmap(void *start, size_t length, int prot, int flags, int fd, off_t offset);
return 被映射区的 pointer, success 时
PROT_READ: 页内容可被读取
4. char *getenv(const char *name)
(1) 功能
return 以 `name 所指 字符串` 为 `环境变量名` 的 `环境变量值`
(2) 实现
name: 字符串常量指针
(3) 调用
char *sha1_file_directory = getenv(DB_ENVIRONMENT) ? : DEFAULT_DB_ENVIRONMENT;
#define DB_ENVIRONMENT "SHA1_FILE_DIRECTORY"
#define DEFAULT_DB_ENVIRONMENT ".dircache/objects"
5 C 语言
1. 内存分配相关 <stdlib.h>
指向 已(重新 realloc)分配 的 内存, 内存分配成功
/
return ptr
\
= NULL, else
(1) malloc
void *malloc(size_t memBlockSize)
(2) calloc
void *calloc(size_t nElemNum, size_t elemSize)
与 malloc 相比, 会 设 分配的内存 为 零
(3) realloc
void *realloc(void *ptr, size_t memBlockSize)
尝试 重新 调整(分配) 之前 调用 malloc / calloc / realloc 所分配的 ptr 所指 内存块 的大小
2. C <string.h> / C++ <cstring> mem 系列函数
(1) memcmp
int memcmp(const void *s1, const void *s2, size_t nbytes)
返回值:
== 0, s1 == s2
< 0, s1 < s2
> 0, s1 > s2
(2) memmove / memcpy
void *memmove( void* dst, const void* src, size_t nbytes );
void *memcpy(void *dst, void *src, size_t nbytes);
返回值:
dst
(3) memset
void *memset(void *dst, int ch, size_t nbytes)
返回值:
dst
对 `较大结构体` 或 `数组` 清零的一种 `最快方法`
note:
按 字节(ch 的 低 8位 : -2^7 ~ 2^7 - 1 = -128 ~ 127) 对 内存块 初始化
3. fprintf / printf / sprintf / snprintf
`从右到左:` 将 data `按 格式化输出` wite 到 `stream / stdout / char* 所指 memory`
int fprintf(FILE *stream, const char *format, ...)
int printf( const char *format, ...)
int sprintf(char *str, const char *format, ...)
int snprintf(char *str, size_t size, const char *format, ...)`
`超过 size 会被截断`
`printf: 默认 无缓冲`
sprintf / snprintf:
1) 对 format 中
最后一个 %s:
无 '\0' -> 加上'\0'
有 '\0' -> 保留
其他 %s:
去 '\0'
2) 效率 高于 字符串操作函数
3) 更灵活: 可将 想要的结果 输出到指定 字符串 / char* buf 空间
网友评论