0%

go get 代理

代理服务端

要把 go get 请求转发别的 repo 上,需要利用 go get 的 discovery 特性去动态查找 repo。

首先要知道 go get 做了什么,定位到 repoRootForImportDynamic 函数(源文件 go/src/cmd/go/internal/get/vcs.go),可以知道命令将 ImportPath 作为 url 发起了一次请求(web.GetMaybeInsecure),并且将获取的到结果使用 parseMetaGoImports 函数(源文件 go/src/cmd/go/internal/get/discovery.go)解析。
根据 parseMetaGoImports 函数可以得知,结果作为 xml 解析,并且在查找所有 meta 元素是否存在 name 属性值为 go-import,如果存在则解析 content 属性值,拆分为 PrefixVCSRepoRoot

那我们可以明确知道了,我们需要返回一个 xml,内容格式可能是这样的

1
2
3
4
5
<html>
<head>
<meta name="go-import" content="PREFIX VCS REPOROOT" />
</head>
</html>

然后一个简单的可配置的 https go-get 服务端完成了

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
package main

import (
"encoding/json"
"io/ioutil"
"log"
"net/http"
"path"
"regexp"
"text/template"
)

type Meta struct {
re *regexp.Regexp
Pattern string `json:"pattern"`
Pkg string `json:"pkg"`
VCS string `json:"vcs"`
Repo string `json:"repo"`
Source string `json:"source"`
SourceDir string `json:"sourcedir"`
SourceLine string `json:"sourceline"`
Doc string `json:"doc"`
Body string `json:"body"`
}

var metatpl = template.Must(template.New("meta").Parse(`<!DOCTYPE html>
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8"/>
<meta name="go-import" content="{{.Pkg}} {{.VCS}} {{.Repo}}"/>
{{- if .Source}}
<meta name="go-source" content="{{.Pkg}} {{.Source}} {{.SourceDir}} {{.SourceLine}}"/>
{{- end}}
{{- if .Doc}}
<meta http-equiv="refresh" content="0; url={{.Doc}}"/>
{{- end}}
</head>
<body>
{{- if .Body}}
{{.Body}}
{{- end}}
</body>
</html>
`))

var pkgs map[string]*Meta

func getpkg(w http.ResponseWriter, r *http.Request) {
if r.Method != "GET" {
http.Error(w, "Method Not Allowed", http.StatusMethodNotAllowed)
return
}
if r.FormValue("go-get") != "1" {
http.Error(w, "Bad Request", http.StatusBadRequest)
return
}
pkg := path.Join(r.Host, r.URL.Path)

log.Printf("get %s", pkg)

meta := pkgs[pkg]
if meta == nil {
for _, m := range pkgs {
if m.re != nil && m.re.MatchString(pkg) {
meta = m
break
}
}
}
if meta == nil {
http.Error(w, "Not Found", http.StatusNotFound)
return
}
metatpl.Execute(w, meta)
}

func loadmeta(filename string) error {
data, err := ioutil.ReadFile(filename)
if err != nil {
return err
}
var allmeta []*Meta
err = json.Unmarshal(data, &allmeta)
if err != nil {
return err
}
pkgs = make(map[string]*Meta, len(allmeta))
for _, m := range allmeta {
if m.Pattern != "" {
m.re = regexp.MustCompile(m.Pattern)
}
pkgs[m.Pkg] = m
}
return nil
}

func main() {
err := loadmeta("./meta.json")
if err != nil {
log.Fatalln(err)
}
err = http.ListenAndServeTLS(":443", "./cart.pem", "./key.pri", http.HandlerFunc(getpkg))
if err != nil {
log.Fatalln(err)
}
}

具体的输出内容,我是参考 curl 从 golang.org 拉取的结果调整的,问题不大,go https 服务端需要的证书和私钥文件生成是可以参考 Tony Bai 的文章

实际应用

我用这个服务代理所有对 golang.org/x/tools 的 get 请求,配置如下

1
2
3
4
5
6
7
8
9
10
11
[
{
"pattern": "golang.org/x/tools/.*",
"pkg": "golang.org/x/tools",
"vcs": "git",
"repo": "https://github.com/golang/tools",
"source": "https://github.com/golang/tools/",
"sourcedir": "https://github.com/golang/tools/tree/master{/dir}",
"sourceline": "https://github.com/golang/tools/blob/master{/dir}/{file}#L{line}"
}
]

过程中遇到了几个问题,也是 Tony Bai 文章中提到的。

  1. bad certificate

    这个问题比较好解决,生成的证书 Common Name 不匹配,直接修改。

  2. unknown certificate authority

    这个比较难解决,好在 go get 提供了一个 -insecure 的命令允许 tls 建立连接过程跳过对证书的 CA 的校验。但这个做法只能在手动操作下比较好操作,如果走集成的命令,比如 vim-go 的 GoUpdateBinaries 命令的话,就要去改 vim-go 的 plugin 源码了。其实还有一种方式,如果只是我们私人使用的话,直接让系统 CA 信任我们自签的证书就完全没毛病了。(或者找黑心证书商买,大雾

  3. 多域名
    网上文章好好找找,问题不大。

redis RENAME 命令按文档说法是存在一个隐式 DEL 操作,通过查阅代码 db.c 可以得知至少一次 dbDelete,至多两次 dbDelete。

在命令上 redis 是提供了两种删除的操作,DELUNLINK,分别对应了 dbSyncDeletedbAsyncDelete

dbDelete 是对 dbAsyncDelete/dbSyncDelete 的封装,并且由配置 lazyfree_lazy_expire 决定,两个函数区别 dictGenericDelete 是否在执行线程 free K/V pair 和 dict key 内存。

安装

最近打算博客转 https, 有什么好处就不多说了, 反正是没人看的博客, 转了也不会有什么性能问题(笑).
在我自己的博客上使用 let’s encrypt 证书还是非常方便的, 官方的文档和 certbot, 直接就迁移到了 https.
我这里就列一下 Ubuntu 16.04 - Nginx 环境下的命令流程, 但是最好以文档为主.

1
2
3
4
sudo add-apt-repository ppa:certbot/certbot
sudo apt-get update
sudo apt-get install python-certbot-nginx
sudo certbot --nginx

然后根据自己的需要配置下 certbot 选项.

看到 Congratulations 基本可以认为成功了. 这时候访问博客已经变成了 https. typecho 大部分情况都适应的良好, 开启 f12 发现有一个资源被 blocking, 直接在代码里改成 https 就行. 有必要的话可以进管理后台更新一下站点信息到 https.

自动更新证书

certbot 会自动配置 cron, 大概是每天 0/12 点调用 certbot renew, 这个命令会检查和更新时间少于 30 天的证书, 不需要额外配置.

go 全局的 rand 是线程安全的, 通过 mutex 来保证, 但是 go 提供的 rand.NewSource 使用的 rngSource 并不是线程安全的
这里提供一种基于 TLS 的实现

mtrnd.go

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
package mtrnd

import (
"math/rand"
"sync"
"time"

"github.com/vizee/asm/hack"
)

var (
rndmu sync.Mutex
rnds []*rand.Rand
)

func currnd() *rand.Rand {
pid := hack.ProcPin()
if pid >= len(rnds) {
hack.ProcUnpin()
rndmu.Lock()
pid = hack.ProcPin()
if pid >= len(rnds) {
t := make([]*rand.Rand, pid+1)
n := copy(t, rnds)
for i := n; i < len(t); i++ {
t[i] = rand.New(rand.NewSource(time.Now().UnixNano() ^ int64(i)))
}
rnds = t
}
rndmu.Unlock()
}
r := rnds[pid]
hack.ProcUnpin()
return r
}

func Int() int {
return currnd().Int()
}

func Intn(n int) int {
return currnd().Intn(n)
}

func Uint64() uint64 {
return currnd().Uint64()
}

mtrnd_test.go:

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
49
50
51
52
53
package mtrnd

import (
"math/rand"
"testing"
)

func TestMT(t *testing.T) {
var n [256]int
for i := 0; i < 1000000; i++ {
n[Intn(256)]++
}
min := n[0]
max := n[0]
for i := 0; i < 256; i++ {
if n[i] < min {
min = n[i]
}
if n[i] > max {
max = n[i]
}
t.Log(n[i])
}
t.Log("diff", max-min)
}

func BenchmarkGlobal(b *testing.B) {
for i := 0; i < b.N; i++ {
_ = rand.Int()
}
}

func BenchmarkMT(b *testing.B) {
for i := 0; i < b.N; i++ {
_ = Int()
}
}

func BenchmarkGlobalP(b *testing.B) {
b.RunParallel(func(pb *testing.PB) {
for pb.Next() {
_ = rand.Int()
}
})
}

func BenchmarkMTP(b *testing.B) {
b.RunParallel(func(pb *testing.PB) {
for pb.Next() {
_ = Int()
}
})
}

benchmark result (i7 4c8t):

1
2
3
4
BenchmarkGlobal-8    	50000000	        32.5 ns/op
BenchmarkMT-8 50000000 29.4 ns/op
BenchmarkGlobalP-8 10000000 170 ns/op
BenchmarkMTP-8 200000000 7.06 ns/op

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
package gorpool

import (
"sync"
"time"
)

type gor struct {
ch chan func()
idx int
}

type Pool struct {
mu sync.Mutex
idle []*gor
Reserve uint
}

func reserve(kb uint) {
var stack [1024]byte
_ = stack[1023]
if kb <= 1 {
return
}
reserve(kb - 1)
}

func (p *Pool) gorproc(g *gor) {
// only a new gor reserves stack
if r := p.Reserve; r >= 1024 {
reserve(r / 1024)
}
tm := time.NewTimer(time.Minute)
down := false
for !down {
tm.Reset(time.Minute)
select {
case fn := <-g.ch:
fn()
p.mu.Lock()
g.idx = len(p.idle)
p.idle = append(p.idle, g)
p.mu.Unlock()
case <-tm.C:
p.mu.Lock()
if g.idx >= 0 {
t := p.idle[len(p.idle)-1]
t.idx = g.idx
p.idle[t.idx] = t
p.idle = p.idle[:len(p.idle)-1]
down = true
}
p.mu.Unlock()
}
}
}

func (p *Pool) Go(fn func()) {
if fn == nil {
panic("nil func")
}
var g *gor
p.mu.Lock()
if len(p.idle) > 0 {
g = p.idle[len(p.idle)-1]
p.idle = p.idle[:len(p.idle)-1]
g.idx = -1
}
p.mu.Unlock()
if g == nil {
g = &gor{
ch: make(chan func(), 1),
idx: -1,
}
go p.gorproc(g)
}
g.ch <- fn
}

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
49
50
51
52
53
import (
"encoding/binary"
"fmt"
"net"
"strconv"
"unsafe"
)

func htons(w uint16) uint16 {
return w>>8 | w<<8
}

func resolveaddr(address string) (af int, sa interface{}, size uintptr, err error) {
var addr *net.TCPAddr
addr, err = net.ResolveTCPAddr("tcp", address)
if err != nil {
return
}
ip := addr.IP
if len(ip) == 0 {
ip = net.IPv4zero
}
if len(ip) == net.IPv4len {
af = AF_INET
sa = &sockaddr_in{
sin_family: AF_INET,
sin_port: htons(uint16(addr.Port)),
sin_addr: binary.BigEndian.Uint32(ip),
}
size = unsafe.Sizeof(sockaddr_in{})
} else if len(ip) == net.IPv6len {
af = AF_INET6
scopeid := uint32(0)
nif, err := net.InterfaceByName(addr.Zone)
if err == nil {
scopeid = uint32(nif.Index)
} else {
n, _ := strconv.Atoi(addr.Zone)
scopeid = uint32(n)
}
sin6 := &sockaddr_in6{
sin6_family: AF_INET6,
sin6_port: htons(uint16(addr.Port)),
sin6_scope_id: scopeid,
}
copy(sin6.sin6_addr[:], ip)
sa = sin6
size = unsafe.Sizeof(sockaddr_in6{})
} else {
err = fmt.Errorf("unrecognized address: %s", address)
}
return
}

基于 go 自带的 parser/ast 库, 解析 go 源码提取一些信息,生成汇编 SYSCALL
gensyscall.go
win32 库之前是纯字符串解析, 这种做法并不好, 所以也打算替换成使用基于 ast 的解析方式

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
package main

import (
"flag"
"fmt"
"go/ast"
"go/parser"
"go/token"
"html/template"
"io/ioutil"
"os"
"os/exec"
"regexp"
"strconv"
"strings"
)

const templateGoFunc = `func {{.Name -}}
({{range $i, $e := .Params -}}
{{with $e}}{{if $i}}, {{end}}{{.Name}} {{.Type}}{{end}}
{{- end}}){{if .Results | len | lt 1}} (
{{- range $i, $e := .Results -}}
{{with $e}}{{if $i}}, {{end}}{{if .Name | len}}{{.Name}} {{end}}{{.Type}}{{end}}
{{- end}})
{{- else if .Results | len | eq 1 -}}
{{with index .Results 0}}{{if .Name | len}} ({{.Name}} {{.Type}}){{else}} {{.Type}}{{end}}{{end}}
{{- end}}`

const templateLinuxAMD64 = `// generated by gensyscall.go
// GOFILE={{.GOFILE}} GOPACKAGE={{.GOPACKAGE}} GOOS={{.GOOS}} GOARCH={{.GOARCH}}
// DO NOT EDIT!

#include "textflag.h"

{{range .Funcs -}}
// {{template "gofunc" .}}
TEXT ·{{.Name}}(SB), NOSPLIT, $0-{{.FrameSize}}
{{- if .Blocking}}
CALL runtime·entersyscall(SB)
{{- end -}}
{{range $i, $e := .Params -}}
{{with $e}}
MOV{{.Size | SizeToChar}} {{.Name}}+{{.Offset}}(FP), {{$i | ArgToReg}}
{{- end}}
{{- end}}
MOVQ ${{.Trap}}, AX
SYSCALL
{{- range $i, $e := .Results -}}
{{with $e}}
MOV{{.Size | SizeToChar}} {{$i | ResToReg}}, {{.Label}}+{{.Offset}}(FP){{end}}
{{- end}}{{- if .Blocking}}
CALL runtime·exitsyscall(SB)
{{- end}}
RET

{{end}}`

var sizes = map[string]int{
"int": 8,
"uint": 8,
"int8": 1,
"uint8": 1,
"int16": 2,
"uint16": 2,
"int32": 4,
"uint32": 4,
"int64": 8,
"uint64": 8,
"uintptr": 8,
"byte": 1,
"bool": 1,
"unsafe.Pointer": 8,
"syscall.Handle": 8,
}

func sizeof(typ string) int {
if typ[0] == '*' {
return 8
}
return sizes[typ]
}

var systraps = map[string]int{}

func fucksystraps() {
data, err := ioutil.ReadFile("/usr/include/x86_64-linux-gnu/asm/unistd_64.h")
if err != nil {
panic(err)
}
re := regexp.MustCompile(`#define\s+__NR_([_a-zA-Z0-9]+)\s+(\d+)`)
for _, submatch := range re.FindAllSubmatch(data, -1) {
systraps[string(submatch[1])], _ = strconv.Atoi(string(submatch[2]))
}
}

var isblocking = map[string]bool{}

const stackalign = 8

type fielddecl struct {
Name string
Type string
Offset int
Size int
Label string
}

type funcdecl struct {
Name string
Blocking bool
Trap int
FrameSize int
Params []*fielddecl
Results []*fielddecl
}

func align(n, a int) int {
return (n + a - 1) &^ (a - 1)
}

func (fn *funcdecl) preprocess() {
if len(fn.Results) > 2 {
panic(fmt.Sprintf("surprise motherfucker: %d", len(fn.Results)))
}
fn.Blocking = isblocking[fn.Name]
var ok bool
fn.Trap, ok = systraps[fn.Name]
if !ok {
panic(fmt.Sprintf("surprise motherfucker: %s", fn.Name))
}
size := 0
for i := range fn.Params {
param := fn.Params[i]
n := sizeof(param.Type)
if n == 0 {
panic(fmt.Sprintf("surprise motherfucker: %s", param.Type))
}
size = align(size, n)
param.Offset = size
param.Size = n
size += n
}
size = align(size, stackalign)
for i := range fn.Results {
result := fn.Results[i]
n := sizeof(result.Type)
if n == 0 {
panic(fmt.Sprintf("surprise motherfucker: %s", result.Type))
}
size = align(size, n)
if result.Name != "" {
result.Label = result.Name
} else if i == 0 {
result.Label = "ret"
} else {
result.Label = "ret" + strconv.Itoa(i)
}
result.Offset = size
result.Size = n
size += n
}
fn.FrameSize = size
}

func appendExpr(buf []byte, expr ast.Expr) []byte {
switch typ := expr.(type) {
case *ast.Ident:
buf = append(buf, typ.Name...)
case *ast.BasicLit:
buf = append(buf, typ.Value...)
case *ast.SelectorExpr:
buf = append(append(appendExpr(buf, typ.X), '.'), typ.Sel.Name...)
case *ast.ArrayType:
buf = append(buf, '[')
if typ.Len != nil {
buf = appendExpr(buf, typ.Len)
}
buf = appendExpr(append(buf, ']'), typ.Elt)
case *ast.StarExpr:
buf = appendExpr(append(buf, '*'), typ.X)
default:
panic(fmt.Sprintf("surprise motherfucker: %#+v", expr))
}
return buf
}

func parseFields(list *ast.FieldList) []*fielddecl {
if list == nil {
return nil
}
buf := make([]byte, 0, 64)
var fields []*fielddecl
for _, field := range list.List {
buf = appendExpr(buf[:0], field.Type)
typ := string(buf)
if field.Names == nil {
fields = append(fields, &fielddecl{Name: "", Type: typ})
} else {
for _, name := range field.Names {
fields = append(fields, &fielddecl{Name: name.Name, Type: typ})
}
}
}
return fields
}

func parseDecl(file string) ([]*funcdecl, error) {
fset := token.NewFileSet()
astf, err := parser.ParseFile(fset, file, nil, parser.DeclarationErrors)
if err != nil {
return nil, err
}

var decls []*funcdecl
for _, decl := range astf.Decls {
fd, ok := decl.(*ast.FuncDecl)
if !ok {
continue
}
decl := &funcdecl{
Name: fd.Name.Name,
Params: parseFields(fd.Type.Params),
Results: parseFields(fd.Type.Results),
}
decl.preprocess()
decls = append(decls, decl)
}
return decls, nil
}

var (
argtoreg = [...]string{
"DI", "SI", "DX", "R10", "R8", "R9",
}
restoreg = [...]string{
"AX", "DX",
}
sizetochar = map[int]string{
1: "B",
2: "W",
4: "L",
8: "Q",
}
)

type sourceData struct {
GOFILE string
GOPACKAGE string
GOOS string
GOARCH string
Funcs []*funcdecl
}

func main() {
var (
blocking string
traps string
data sourceData
)
flag.StringVar(&blocking, "blocking", "", "blocking functions")
flag.StringVar(&traps, "traps", "", "custom syscall trap")
flag.StringVar(&data.GOFILE, "gofile", os.Getenv("GOFILE"), "GOFILE")
flag.StringVar(&data.GOPACKAGE, "gopackage", os.Getenv("GOPACKAGE"), "GOPACKAGE")
flag.StringVar(&data.GOOS, "goos", os.Getenv("GOOS"), "GOOS")
flag.StringVar(&data.GOARCH, "goarch", os.Getenv("GOARCH"), "GOARCH")
flag.Parse()

if data.GOFILE == "" || data.GOPACKAGE == "" {
panic(fmt.Sprintf("missing GOFILE/GOPACKAGE"))
}
if data.GOOS != "linux" || data.GOARCH != "amd64" {
panic(fmt.Sprintf("unsupport platform: %s/%s", data.GOOS, data.GOARCH))
}

for _, s := range strings.Split(blocking, ",") {
s = strings.TrimSpace(s)
if s == "" {
continue
}
isblocking[s] = true
}

fucksystraps()
for _, s := range strings.Split(traps, ",") {
s = strings.TrimSpace(s)
if s == "" {
continue
}
pair := strings.SplitN(s, ":", 2)
if len(pair) != 2 || pair[0] == "" {
continue
}
trap, ok := systraps[pair[1]]
if !ok {
var err error
trap, err = strconv.Atoi(pair[1])
if err != nil {
panic(err)
}
}
systraps[pair[0]] = trap
}

var err error
data.Funcs, err = parseDecl(data.GOFILE)
if err != nil {
panic(err)
}

tpl := template.New("gensyscall")
tpl.Funcs(map[string]interface{}{
"ArgToReg": func(args ...interface{}) string {
return argtoreg[args[0].(int)]
},
"ResToReg": func(args ...interface{}) string {
return restoreg[args[0].(int)]
},
"SizeToChar": func(args ...interface{}) string {
return sizetochar[args[0].(int)]
},
})
template.Must(tpl.New("gofunc").Parse(templateGoFunc))
template.Must(tpl.New("genasm").Parse(templateLinuxAMD64))
outputfile := "syscall_" + data.GOOS + "_" + data.GOARCH + ".s"
f, err := os.Create(outputfile)
if err != nil {
panic(err)
}
defer f.Close()
err = tpl.ExecuteTemplate(f, "genasm", &data)
if err != nil {
panic(err)
}
err = exec.Command("go", "vet").Run()
if err != nil {
panic(err)
}
}

利用 cache 在一些方面做了优化, 总体性能还是不错

这个实现会被合并到 https://github.com/vizee/echo 作为 echo.Var 的输出实现

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
package vardump

import (
"io"
"reflect"
"sync"
"unsafe"

"github.com/vizee/litebuf"
)

var rtcache struct {
sync.RWMutex
types map[reflect.Type]*rtype
}

var bufpool = sync.Pool{
New: func() interface{} {
return &litebuf.Buffer{}
},
}

type rtype struct {
typ string
fields []string
}

func makertype(rt reflect.Type) *rtype {
n := rt.NumField()
t := &rtype{
typ: rt.String(),
fields: make([]string, n),
}
for i := 0; i < n; i++ {
rf := rt.Field(i)
t.fields[i] = rf.Name
if rf.Type.Kind() == reflect.Struct {
if _, ok := rtcache.types[rf.Type]; !ok {
makertype(rf.Type)
}
}
}
rtcache.types[rt] = t
return t
}

func getrtype(rt reflect.Type) *rtype {
rtcache.RLock()
t := rtcache.types[rt]
rtcache.RUnlock()

if t == nil {
rtcache.Lock()
t = rtcache.types[rt]
if t == nil {
t = makertype(rt)
}
rtcache.Unlock()
}
return t
}

type vari struct {
maxDeep int
deep int
buf *litebuf.Buffer
}

func (v *vari) dumpStruct(rv reflect.Value) {
rt := getrtype(rv.Type())
v.buf.WriteString(rt.typ)
v.buf.WriteByte('{')
for i := 0; i < len(rt.fields); i++ {
if i > 0 {
v.buf.WriteByte(' ')
}
v.buf.WriteString(rt.fields[i])
v.buf.WriteByte(':')
t := rv.Field(i)
if t.Kind() == reflect.Interface && t.CanInterface() {
v.dump(t.Interface())
} else {
v.dumpValue(t)
}
}
v.buf.WriteByte('}')
}

func (v *vari) dumpMap(rv reflect.Value) {
v.buf.WriteString(`map[`)
keys := rv.MapKeys()
for i := range keys {
if i > 0 {
v.buf.WriteByte(' ')
}
v.dumpValue(keys[i])
v.buf.WriteByte(':')
t := rv.MapIndex(keys[i])
if t.Kind() == reflect.Interface {
v.dump(t.Interface())
} else {
v.dumpValue(t)
}
}
v.buf.WriteByte(']')
}

func (v *vari) dumpArray(rv reflect.Value) {
v.buf.WriteByte('[')
n := rv.Len()
for i := 0; i < n; i++ {
if i > 0 {
v.buf.WriteByte(' ')
}
t := rv.Index(i)
if t.Kind() == reflect.Interface && t.CanInterface() {
v.dump(t.Interface())
} else {
v.dumpValue(t)
}
}
v.buf.WriteByte(']')
}

func (v *vari) dumpValue(rv reflect.Value) {
switch rv.Kind() {
case reflect.Int, reflect.Int8, reflect.Int16, reflect.Int32, reflect.Int64:
v.buf.AppendInt(rv.Int(), 10)
case reflect.Uint, reflect.Uint8, reflect.Uint16, reflect.Uint32, reflect.Uint64, reflect.Uintptr:
v.buf.AppendUint(rv.Uint(), 10)
case reflect.Ptr:
if v.deep < v.maxDeep {
if rv.IsNil() {
v.buf.WriteString("nil")
} else {
v.buf.WriteByte('&')
v.deep++
v.dumpValue(rv.Elem())
v.deep--
}
break
}
fallthrough
case reflect.UnsafePointer, reflect.Chan, reflect.Func:
p := rv.Pointer()
if p == 0 {
v.buf.WriteString("nil")
} else {
v.buf.WriteString("0x")
v.buf.AppendUint(uint64(p), 16)
}
case reflect.Bool:
if rv.Bool() {
v.buf.WriteString("true")
} else {
v.buf.WriteString("false")
}
case reflect.Float32:
v.buf.AppendFloat(rv.Float(), 'g', -1, 32)
case reflect.Float64:
v.buf.AppendFloat(rv.Float(), 'g', -1, 64)
case reflect.String:
v.buf.WriteString(rv.String())
case reflect.Interface:
if rv.IsNil() {
v.buf.WriteString("nil")
} else if rv.CanInterface() && v.deep < v.maxDeep {
v.deep++
v.dumpValue(reflect.ValueOf(rv.Interface()))
v.deep--
} else {
p := rv.InterfaceData()
v.buf.WriteString("{0x")
v.buf.AppendUint(uint64(p[0]), 16)
v.buf.WriteString(",0x")
v.buf.AppendUint(uint64(p[1]), 16)
v.buf.WriteByte('}')
}
case reflect.Complex64, reflect.Complex128:
c := rv.Complex()
v.buf.AppendFloat(real(c), 'g', -1, 64)
v.buf.WriteByte('+')
v.buf.AppendFloat(imag(c), 'g', -1, 64)
v.buf.WriteByte('i')
case reflect.Map:
if rv.IsNil() {
v.buf.WriteString("nil")
} else {
v.dumpMap(rv)
}
case reflect.Struct:
v.dumpStruct(rv)
case reflect.Array, reflect.Slice:
v.dumpArray(rv)
default:
v.buf.WriteString("<invalid kind>")
}
}

func (v *vari) dump(x interface{}) {
switch t := x.(type) {
case nil:
v.buf.WriteString("nil")
case int:
v.buf.AppendInt(int64(t), 10)
case int8:
v.buf.AppendInt(int64(t), 10)
case int16:
v.buf.AppendInt(int64(t), 10)
case int32:
v.buf.AppendInt(int64(t), 10)
case int64:
v.buf.AppendInt(t, 10)
case uint:
v.buf.AppendUint(uint64(t), 10)
case uint8:
v.buf.AppendUint(uint64(t), 10)
case uint16:
v.buf.AppendUint(uint64(t), 10)
case uint32:
v.buf.AppendUint(uint64(t), 10)
case uint64:
v.buf.AppendUint(t, 10)
case uintptr:
v.buf.AppendUint(uint64(t), 10)
case float32:
v.buf.AppendFloat(float64(t), 'g', -1, 32)
case float64:
v.buf.AppendFloat(t, 'g', -1, 64)
case bool:
if t {
v.buf.WriteString("true")
} else {
v.buf.WriteString("false")
}
case unsafe.Pointer:
v.buf.WriteString("0x")
v.buf.AppendUint(uint64(uintptr(t)), 16)
case string:
v.buf.WriteString(t)
case reflect.Value:
v.dumpValue(t)
default:
v.dumpValue(reflect.ValueOf(t))
}
}

func Dump(w io.Writer, x interface{}) {
buf := bufpool.Get().(*litebuf.Buffer)
v := vari{
maxDeep: 1,
buf: buf,
}
v.dump(x)
w.Write(buf.Bytes())
bufpool.Put(buf)
}

func init() {
rtcache.types = make(map[reflect.Type]*rtype)
}

hdu 2222 AC 自动机
传送门:http://acm.hdu.edu.cn/showproblem.php?pid=2222

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#include <stdio.h>

#define N 500051
#define CHARSET_SIZE 26
#define NIL 0
#define ROOT 1

int alloc;
int trans[N][CHARSET_SIZE];
int fails[N];
int counts[N];

int qhead, qtail;
int queue[N];

char str[1000001];
char keyword[51];

int ac_alloc() {
int n = alloc++;
for (int c = 0; c < CHARSET_SIZE; c++) {
trans[n][c] = NIL;
}
counts[n] = 0;
return n;
}

void ac_insert(char *s) {
int n = ROOT;
for (int i = 0; s[i]; i++) {
int c = s[i] - 'a';
if (trans[n][c] == NIL) {
trans[n][c] = ac_alloc();
}
n = trans[n][c];
}
counts[n]++;
}

void ac_build_fails() {
qhead = qtail = 0;
fails[ROOT] = NIL;
for (int i = 0; i < CHARSET_SIZE; i++) {
if (trans[ROOT][i] != NIL) {
fails[trans[ROOT][i]] = ROOT;
queue[qtail++] = trans[ROOT][i];
}
}
while (qhead < qtail) {
int n = queue[qhead++];
for (int i = 0; i < CHARSET_SIZE; i++) {
if (trans[n][i] == NIL) {
continue;
}
int fail = fails[n];
while (fail != NIL) {
if (trans[fail][i] != NIL) {
fails[trans[n][i]] = trans[fail][i];
break;
}
fail = fails[fail];
}
if (fail == NIL) {
fails[trans[n][i]] = ROOT;
}
queue[qtail++] = trans[n][i];
}
}
}

int ac_match(char *s) {
int total = 0;
int n = ROOT;
for (int i = 0; s[i]; i++) {
int c = s[i] - 'a';
while (trans[n][c] == NIL && n != ROOT) {
n = fails[n];
}
n = trans[n][c];
if (n == NIL) {
n = ROOT;
}
int t = n;
while (t != ROOT && counts[t] != -1) {
total += counts[t];
counts[t] = -1;
t = fails[t];
}
}
return total;
}

int main() {
int t;

scanf("%d", &t);
while (t--) {
alloc = ROOT;
ac_alloc();
int w;
scanf("%d", &w);
while (w--) {
scanf("%s", keyword);
ac_insert(keyword);
}
ac_build_fails();
scanf("%s", str);
printf("%d\n", ac_match(str));
}
return 0;
}

linux CPU 用量保存在 /proc/stat 文件里。
4.4 内核已经拓展到十元组,通过

1
man proc

可以知道分别时是 user nice system idle iowait irq softirq steal guest guest_nice

go 实现

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
package main

import (
"encoding/binary"
"fmt"
"os"
"time"
)

var fstat *os.File

func getcpuusage() (int, int) {
fd := fstat
if fd == nil {
var err error
fd, err = os.Open("/proc/stat")
if err != nil {
return -1, -1
}
fstat = fd
}
var stat [128]byte
fd.Seek(0, os.SEEK_SET)
n, err := fd.Read(stat[:])
if fd != fstat {
fd.Close()
}
if err != nil || binary.LittleEndian.Uint32(stat[:4]) != 0x20757063 {
return -1, -1
}
total := 0
idle := 0
usage := 0
idx := 0
ok := false
eol := false
for i := 4; i < n; i++ {
c := stat[i]
if c == '\n' {
total += usage
eol = true
break
}
if '0' <= c && c <= '9' {
usage *= 10
usage += int(c) - '0'
ok = true
} else if ok {
total += usage
if idx == 3 {
idle = usage
}
usage = 0
idx++
ok = false
}
}
if !eol {
return -1, -1
}
return total, idle
}

func main() {
prevtotal, previdle := 0, 0
for {
total, idle := getcpuusage()
usage := 100 - 100*(idle-previdle)/(total-prevtotal+1)
fmt.Println(usage)
prevtotal, previdle = total, idle
time.Sleep(time.Second)
}
}