分类 软件开发 下的文章

写 Go 的人往往对它的错误处理模式有一定的看法。按不同的语言经验,人们可能有不同的习惯处理方法。这就是为什么我决定要写这篇文章,尽管有点固执己见,但我认为听取我的经验是有用的。我想要讲的主要问题是,很难去强制执行良好的错误处理实践,错误经常没有堆栈追踪,并且错误处理本身太冗长。不过,我已经看到了一些潜在的解决方案,或许能帮助解决一些问题。

与其他语言的快速比较

在 Go 中,所有的错误都是值。因为这点,相当多的函数最后会返回一个 error, 看起来像这样:

func (s *SomeStruct) Function() (string, error)

因此这导致调用代码通常会使用 if 语句来检查它们:

bytes, err := someStruct.Function()
if err != nil {
  // Process error
}

另外一种方法,是在其他语言中,如 Java、C#、Javascript、Objective C、Python 等使用的 try-catch 模式。如下你可以看到与先前的 Go 示例类似的 Java 代码,声明 throws 而不是返回 error

public String function() throws Exception

它使用的是 try-catch 而不是 if err != nil

try {
  String result = someObject.function()
  // continue logic
}
catch (Exception e) {
  // process exception
}

当然,还有其他的不同。例如,error 不会使你的程序崩溃,然而 Exception 会。还有其他的一些,在本篇中会专门提到这些。

实现集中式错误处理

退一步,让我们看看为什么要在一个集中的地方处理错误,以及如何做到。

大多数人或许会熟悉的一个例子是 web 服务 - 如果出现了一些未预料的的服务端错误,我们会生成一个 5xx 错误。在 Go 中,你或许会这么实现:

func init() {
    http.HandleFunc("/users", viewUsers)
    http.HandleFunc("/companies", viewCompanies)
}

func viewUsers(w http.ResponseWriter, r *http.Request) {
    user // some code
    if err := userTemplate.Execute(w, user); err != nil {
        http.Error(w, err.Error(), 500)
    }
}

func viewCompanies(w http.ResponseWriter, r *http.Request) {
    companies = // some code
    if err := companiesTemplate.Execute(w, companies); err != nil {
        http.Error(w, err.Error(), 500)
    }
}

这并不是一个好的解决方案,因为我们不得不重复地在所有的处理函数中处理错误。为了能更好地维护,最好能在一处地方处理错误。幸运的是,在 Go 语言的官方博客中,Andrew Gerrand 提供了一个替代方法,可以完美地实现。我们可以创建一个处理错误的 Type:

type appHandler func(http.ResponseWriter, *http.Request) error

func (fn appHandler) ServeHTTP(w http.ResponseWriter, r *http.Request) {
    if err := fn(w, r); err != nil {
        http.Error(w, err.Error(), 500)
    }
}

这可以作为一个封装器来修饰我们的处理函数:

func init() {
    http.Handle("/users", appHandler(viewUsers))
    http.Handle("/companies", appHandler(viewCompanies))
}

接着我们需要做的是修改处理函数的签名来使它们返回 errors。这个方法很好,因为我们做到了 DRY 原则,并且没有重复使用不必要的代码 - 现在我们可以在单独一个地方返回默认错误了。

错误上下文

在先前的例子中,我们可能会收到许多潜在的错误,它们中的任何一个都可能在调用堆栈的许多环节中生成。这时候事情就变得棘手了。

为了演示这点,我们可以扩展我们的处理函数。它可能看上去像这样,因为模板执行并不是唯一一处会发生错误的地方:

func viewUsers(w http.ResponseWriter, r *http.Request) error {
    user, err := findUser(r.formValue("id")) 
    if err != nil {
      return err;
    }
    return userTemplate.Execute(w, user);
}

调用链可能会相当深,在整个过程中,各种错误可能在不同的地方实例化。Russ Cox的这篇文章解释了如何避免遇到太多这类问题的最佳实践:

“在 Go 中错误报告的部分约定是函数包含相关的上下文,包括正在尝试的操作(比如函数名和它的参数)。”

这个给出的例子是对 OS 包的一个调用:

err := os.Remove("/tmp/nonexist")
fmt.Println(err)

它会输出:

remove /tmp/nonexist: no such file or directory

总结一下,执行后,输出的是被调用的函数、给定的参数、特定的出错信息。当在其他语言中创建一个 Exception 消息时,你也可以遵循这个实践。如果我们在 viewUsers 处理中坚持这点,那么几乎总是能明确错误的原因。

问题来自于那些不遵循这个最佳实践的人,并且你经常会在第三方的 Go 库中看到这些消息:

Oh no I broke

这没什么帮助 - 你无法了解上下文,这使得调试很困难。更糟糕的是,当这些错误被忽略或返回时,这些错误会被备份到堆栈中,直到它们被处理为止:

if err != nil {
  return err
}

这意味着错误何时发生并没有被传递出来。

应该注意的是,所有这些错误都可以在 Exception 驱动的模型中发生 - 糟糕的错误信息、隐藏异常等。那么为什么我认为该模型更有用?

即便我们在处理一个糟糕的异常消息,我们仍然能够了解它发生在调用堆栈中什么地方。因为堆栈跟踪,这引发了一些我对 Go 不了解的部分 - 你知道 Go 的 panic 包含了堆栈追踪,但是 error 没有。我推测可能是 panic 会使你的程序崩溃,因此需要一个堆栈追踪,而处理错误并不会,因为它会假定你在它发生的地方做一些事。

所以让我们回到之前的例子 - 一个有糟糕错误信息的第三方库,它只是输出了调用链。你认为调试会更容易吗?

panic: Oh no I broke
[signal 0xb code=0x1 addr=0x0 pc=0xfc90f]

goroutine 1103 [running]:
panic(0x4bed00, 0xc82000c0b0)
/usr/local/go/src/runtime/panic.go:481 +0x3e6
github.com/Org/app/core.(_app).captureRequest(0xc820163340, 0x0, 0x55bd50, 0x0, 0x0)
/home/ubuntu/.go_workspace/src/github.com/Org/App/core/main.go:313 +0x12cf
github.com/Org/app/core.(_app).processRequest(0xc820163340, 0xc82064e1c0, 0xc82002aab8, 0x1)
/home/ubuntu/.go_workspace/src/github.com/Org/App/core/main.go:203 +0xb6
github.com/Org/app/core.NewProxy.func2(0xc82064e1c0, 0xc820bb2000, 0xc820bb2000, 0x1)
/home/ubuntu/.go_workspace/src/github.com/Org/App/core/proxy.go:51 +0x2a
github.com/Org/app/core/vendor/github.com/rusenask/goproxy.FuncReqHandler.Handle(0xc820da36e0, 0xc82064e1c0, 0xc820bb2000, 0xc5001, 0xc820b4a0a0)
/home/ubuntu/.go_workspace/src/github.com/Org/app/core/vendor/github.com/rusenask/goproxy/actions.go:19 +0x30

我认为这可能是 Go 的设计中被忽略的东西 - 不是所有语言都不会忽视的。

如果我们使用 Java 作为一个随意的例子,其中人们犯的一个最愚蠢的错误是不记录堆栈追踪:

LOGGER.error(ex.getMessage()) // 不记录堆栈追踪
LOGGER.error(ex.getMessage(), ex) // 记录堆栈追踪

但是 Go 似乎在设计中就没有这个信息。

在获取上下文信息方面 - Russ 还提到了社区正在讨论一些潜在的接口用于剥离上下文错误。关于这点,了解更多或许会很有趣。

堆栈追踪问题解决方案

幸运的是,在做了一些查找后,我发现了这个出色的 Go 错误库来帮助解决这个问题,来给错误添加堆栈跟踪:

if errors.Is(err, crashy.Crashed) {
  fmt.Println(err.(*errors.Error).ErrorStack())
}

不过,我认为这个功能如果能成为语言的 第一类公民 first class citizenship 将是一个改进,这样你就不必做一些类型修改了。此外,如果我们像先前的例子那样使用第三方库,它可能没有使用 crashy - 我们仍有相同的问题。

我们对错误应该做什么?

我们还必须考虑发生错误时应该发生什么。这一定有用,它们不会让你的程序崩溃,通常也会立即处理它们:

err := method()
if err != nil {
  // some logic that I must do now in the event of an error!
}

如果我们想要调用大量方法,它们会产生错误,然后在一个地方处理所有错误,这时会发生什么?看上去像这样:

err := doSomething()
if err != nil {
  // handle the error here
}

func doSomething() error {
  err := someMethod()
  if err != nil {
    return err
  }
  err = someOther()
  if err != nil {
    return err
  }
  someOtherMethod()
}

这感觉有点冗余,在其他语言中你可以将多条语句作为一个整体处理。

try {
  someMethod()
  someOther()
  someOtherMethod()
}
catch (Exception e) {
  // process exception
}

或者只要在方法签名中传递错误:

public void doSomething() throws SomeErrorToPropogate {
  someMethod()
  someOther()
  someOtherMethod()
}

我个人认为这两个例子实现了一件事情,只是 Exception 模式更少冗余,更加弹性。如果有什么的话,我觉得 if err!= nil 感觉像样板。也许有一种方法可以清理?

将失败的多条语句做为一个整体处理错误

首先,我做了更多的阅读,并在 Rob Pike 写的 Go 博客中发现了一个比较务实的解决方案。

他定义了一个封装了错误的方法的结构体:

type errWriter struct {
    w   io.Writer
    err error
}

func (ew *errWriter) write(buf []byte) {
    if ew.err != nil {
        return
    }
    _, ew.err = ew.w.Write(buf)
}

让我们这么做:

ew := &errWriter{w: fd}
ew.write(p0[a:b])
ew.write(p1[c:d])
ew.write(p2[e:f])
// and so on
if ew.err != nil {
    return ew.err
}

这也是一个很好的方案,但是我感觉缺少了点什么 - 因为我们不能重复使用这个模式。如果我们想要一个含有字符串参数的方法,我们就不得不改变函数签名。或者如果我们不想执行写操作会怎样?我们可以尝试使它更通用:

type errWrapper struct {
    err error
}
func (ew *errWrapper) do(f func() error) {
    if ew.err != nil {
        return
    }
    ew.err = f();
}

但是我们有一个相同的问题,如果我们想要调用含有不同参数的函数,它就无法编译了。然而你可以简单地封装这些函数调用:

w := &errWrapper{}

w.do(func() error {
    return someFunction(1, 2);
})

w.do(func() error {
    return otherFunction("foo");
})

err := w.err

if err != nil {
// process error here
}

这可以用,但是并没有太大帮助,因为它最终比标准的 if err != nil 检查带来了更多的冗余。如果有人能提供其他解决方案,我会很有兴趣听。或许这个语言本身需要一些方法来以不那么臃肿的方式传递或者组合错误 - 但是感觉似乎是特意设计成不那么做。

总结

看完这些之后,你可能会认为我在对 error 挑刺儿,由此推论我反对 Go。事实并非如此,我只是将它与我使用 try catch 模型的经验进行比较。它是一个用于系统编程很好的语言,并且已经出现了一些优秀的工具。仅举几例,有 KubernetesDockerTerraformHoverfly 等。还有小型、高性能、本地二进制的优点。但是,error 难以适应。 我希望我的推论是有道理的,而且一些方案和解决方法可能会有帮助。


作者简介:

Andrew 是 OpenCredo 的顾问,于 2015 年加入公司。Andrew 在多个行业工作多年,开发基于 Web 的企业应用程序。


via: https://opencredo.com/why-i-dont-like-error-handling-in-go

作者:Andrew Morgan 译者:geekpi 校对:jasminepeng

本文由 LCTT 原创编译,Linux中国 荣誉推出

像大多数新手一样,我一开始是在 StackOverflow 上搜索 Git 命令,然后把答案复制粘贴,并没有真正理解它们究竟做了什么。

Image credit: XKCD

我曾经想过:“如果有一个最常见的 Git 命令的列表,以及它们的功能是什么,这不是极好的吗?”

多年之后,我编制了这样一个列表,并且给出了一些最佳实践,让新手们甚至中高级开发人员都能从中发现有用的东西。

为了保持实用性,我将这个列表与我过去一周实际使用的 Git 命令进行了比较。

几乎每个开发人员都在使用 Git,当然很可能是 GitHub。但大多数开发者大概有 99% 的时间只是使用这三个命令:

git add --all
git commit -am "<message>"
git push origin master

如果你只是单枪匹马,或者参加一场黑客马拉松或开发一次性的应用时,它工作得很好,但是当稳定性和可维护性开始成为一个优先考虑的事情后,清理提交、坚持分支策略和提交信息的规范性就变得很重要。

我将从常用命令的列表开始,使新手更容易了解 Git 能做什么,然后进入更高级的功能和最佳实践。

经常使用的命令

要想在 仓库 repo 中初始化 Git,你只需输入以下命令即可。如果你没有初始化 Git,则不能在该仓库内运行任何其他的 Git 命令。

git init

如果你在使用 GitHub,而且正在将代码推送到在线存储的 GitHub 仓库中,那么你正在使用的就是 远程 remote 仓库。该远程仓库的默认名称(也称为别名)为 origin。如果你已经从 Github 复制了一个项目,它就有了一个 origin。你可以使用命令 git remote -v 查看该 origin,该命令将列出远程仓库的 URL。

如果你初始化了自己的 Git 仓库,并希望将其与 GitHub 仓库相关联,则必须在 GitHub 上创建一个,复制新仓库提供的 URL,并使用 git remote add origin <URL> 命令,这里使用 GitHub 提供的 URL 替换 <URL>。这样,你就可以添加、提交和推送更改到你的远程仓库了。

最后一条命令用在当你需要更改远程仓库时。如果你从其他人那里复制了一个仓库,并希望将远程仓库从原始所有者更改为你自己的 GitHub 帐户。除了改用 set-url 来更改远程仓库外,流程与 git remote add origin 相同。

git remote -v
git remote add origin <url>
git remote set-url origin <url>

复制仓库最常见的方式是使用 git clone,后跟仓库的 URL。

请记住,远程仓库将连接到克隆仓库原属于的帐户。所以,如果你克隆了一个属于别人的仓库,你将无法推送到 GitHub,除非你使用上面的命令改变了 origin

git clone <url>

你很快就会发现自己正在使用分支。如果你还不理解什么是分支,有许多其他更深入的教程,你应该先阅读它们,再继续下面的操作。(这里是一个教程

命令 git branch 列出了本地机器上的所有分支。如果要创建一个新的分支,可以使用命令 git branch <name>,其中 <name> 表示分支的名字,比如说 master

git checkout <name> 命令可以切换到现有的分支。你也可以使用 git checkout -b 命令创建一个新的分支并立即切换到它。大多数人都使用此命令而不是单独的 branchcheckout 命令。

git branch
git branch <name>
git checkout <name>
git checkout -b <name>

如果你对一个分支进行了一系列的更改,假如说此分支名为 develop,如果想要将该分支合并回主分支(master)上,则使用 git merge <branch> 命令。你需要先检出(checkout)主分支,然后运行 git merge developdevelop 合并到主分支中。

git merge <branch>

如果你正在与多个人进行协作,你会发现有时 GitHub 的仓库上已经更新了,但你的本地却没有做相应的更改。如果是这样,你可以使用 git pull origin <branch> 命令从远程分支中拉取最新的更改。

git pull origin <branch>

如果您好奇地想看到哪些文件已被更改以及哪些内存正在被跟踪,可以使用 git status 命令。如果要查看每个文件的更改,可以使用 git diff 来查看每个文件中更改的行。

git status
git diff --stat

高级命令和最佳实践

很快你会到达一个阶段,这时你希望你的提交看起来整洁一致。你可能还需要调整你的提交记录,使得提交更容易理解或者能还原一个意外的有破坏性的更改。

git log 命令可以输出提交的历史记录。你将使用它来查看提交的历史记录。

你的提交会附带消息和一个哈希值,哈希值是一串包含数字和字母的随机序列。一个哈希值示例如下:c3d882aa1aa4e3d5f18b3890132670fbeac912f7

git log

假设你推送了一些可能破坏了你应用程序的东西。你最好回退一个提交然后再提交一次正确的,而不是修复它和推送新的东西。

如果你希望及时回退并从之前的提交中检出(checkout)你的应用程序,则可以使用该哈希作为分支名直接执行此操作。这将使你的应用程序与当前版本分离(因为你正在编辑历史记录的版本,而不是当前版本)。

git checkout c3d88eaa1aa4e4d5f

然后,如果你在那个历史分支中做了更改,并且想要再次推送,你必须使用强制推送。

注意:强制推送是危险的,只有在绝对必要的时候才能执行它。它将覆盖你的应用程序的历史记录,你将失去之后版本的任何信息。

git push -f origin master

在其他时候,将所有内容保留在一个提交中是不现实的。也行你想在尝试有潜在风险的操作之前保存当前进度,或者也许你犯了一个错误,但希望在你的版本历史中避免尴尬地留着这个错误。对此,我们有 git rebase

假设你在本地历史记录上有 4 个提交(没有推送到 GitHub),你要回退这是个提交。你的提交记录看起来很乱很拖拉。这时你可以使用 rebase 将所有这些提交合并到一个简单的提交中。

git rebase -i HEAD~4

上面的命令会打开你计算机的默认编辑器(默认为 Vim,除非你将默认修改为其他的),提供了几个你准备如何修改你的提交的选项。它看起来就像下面的代码:

pick 130deo9 oldest commit message
pick 4209fei second oldest commit message
pick 4390gne third oldest commit message
pick bmo0dne newest commit message

为了合并这些提交,我们需要将 pick 选项修改为 fixup(如代码下面的文档所示),以将该提交合并并丢弃该提交消息。请注意,在 Vim 中,你需要按下 ai 才能编辑文本,要保存退出,你需要按下 Esc 键,然后按 shift + z + z。不要问我为什么,它就是这样。

pick 130deo9 oldest commit message
fixup 4209fei second oldest commit message
fixup 4390gne third oldest commit message
fixup bmo0dne newest commit message

这将把你的所有提交合并到一个提交中,提交消息为 oldest commit message

下一步是重命名你的提交消息。这完全是一个建议的操作,但只要你一直遵循一致的模式,都可以做得很好。这里我建议使用 Google 为 Angular.js 提供的提交指南

为了更改提交消息,请使用 amend 标志。

git commit --amend

这也会打开 Vim,文本编辑和保存规则如上所示。为了给出一个良好的提交消息的例子,下面是遵循该指南中规则的提交消息:

feat: add stripe checkout button to payments page

- add stripe checkout button
- write tests for checkout

保持指南中列出的 类型 type 的一个优点是它使编写更改日志更加容易。你还可以在 页脚 footer (再次,在指南中规定的)中包含信息来引用 问题 issue

注意:如果你正在协作一个项目,并将代码推送到了 GitHub,你应该避免重新引用(rebase)并压缩(squash)你的提交。如果你开始在人们的眼皮子底下更改版本历史,那么你可能会遇到难以追踪的错误,从而给每个人都带来麻烦。

Git 有无数的命令,但这里介绍的命令可能是您最初几年编程所需要知道的所有。


Sam Corcos 是 Sightline Maps 的首席开发工程师和联合创始人,Sightline Maps 是最直观的 3D 打印地形图的平台,以及用于构建 Phoenix 和 React 的可扩展生产应用程序的中级高级教程网站 LearnPhoenix.io。使用优惠码:freecodecamp 取得 LearnPhoenix 的20美元。

(题图:GitHub Octodex


via: https://medium.freecodecamp.org/git-cheat-sheet-and-best-practices-c6ce5321f52

作者:Sam Corcos 译者:firmianay 校对:wxy

本文由 LCTT 原创编译,Linux中国 荣誉推出

探索 哈希表 hash table 的世界并理解其底层的机制是非常有趣的,并且将会受益匪浅。所以,让我们了解它,并从头开始探索吧。

哈希表是许多现代软件应用程序中一种常见的数据结构。它提供了类似字典的功能,使你能够在其中执行插入、删除和删除等操作。这么说吧,比如我想找出“苹果”的定义是什么,并且我知道该定义被存储在了我定义的哈希表中。我将查询我的哈希表来得到定义。它在哈希表内的记录看起来可能像:"苹果" => "一种拥有水果之王之称的绿色水果"。这里,“苹果”是我的关键字,而“一种拥有水果之王之称的水果”是与之关联的值。

还有一个例子可以让我们更清楚,哈希表的内容如下:

"面包" => "固体"
"水" => "液体"
"汤" => "液体"
"玉米片" => "固体"

我想知道面包是固体还是液体,所以我将查询哈希表来获取与之相关的值,该哈希表将返回“固体”给我。现在,我们大致了解了哈希表是如何工作的。使用哈希表需要注意的另一个重要概念是每一个关键字都是唯一的。如果到了明天,我拥有一个面包奶昔(它是液体),那么我们需要更新哈希表,把“固体”改为“液体”来反映哈希表的改变。所以,我们需要添加一条记录到字典中:关键字为“面包”,对应的值为“液体”。你能发现下面的表发生了什么变化吗?(LCTT 译注:不知道这个“面包奶昔”是一种什么食物,大约是一种面包做的奶昔,总之你就理解成作者把液体的“面包奶昔”当成一种面包吧。)

"面包" => "液体"
"水" => "液体"
"汤" => "液体"
"玉米片" => "固体"

没错,“面包”对应的值被更新为了“液体”。

关键字是唯一的,我的面包不能既是液体又是固体。但是,是什么使得该数据结构与其他数据结构相比如此特殊呢?为什么不使用一个数组来代替呢?它取决于问题的本质。对于某一个特定的问题,使用数组来描述可能会更好,因此,我们需要注意的关键点就是,我们应该选择最适合问题的数据结构。例如,如果你需要做的只是存储一个简单的杂货列表,那么使用数组会很适合。考虑下面的两个问题,两个问题的本质完全不同。

  1. 我需要一个水果的列表
  2. 我需要一个水果的列表以及各种水果的价格(每千克)

正如你在下面所看到的,用数组来存储水果的列表可能是更好的选择。但是,用哈希表来存储每一种水果的价格看起来是更好的选择。

//示例数组
["苹果", "桔子", "梨子", "葡萄"]   
//示例哈希表  
{ "苹果" : 3.05,
  "桔子" : 5.5,
  "梨子" : 8.4,
  "葡萄" : 12.4  
}

实际上,有许多的机会需要使用哈希表。

时间以及它对你的意义

这里有篇对时间复杂度和空间复杂度的一个复习

平均情况下,在哈希表中进行搜索、插入和删除记录的时间复杂度均为 O(1) 。实际上,O(1) 读作“大 O 1”,表示常数时间。这意味着执行每一种操作的运行时间不依赖于数据集中数据的数量。我可以保证,查找、插入和删除项目均只花费常数时间,“当且仅当”哈希表的实现方式正确时。如果实现不正确,可能需要花费很慢的 O(n) 时间,尤其是当所有的数据都映射到了哈希表中的同一位置/点。

构建一个好的哈希表

到目前为止,我们已经知道如何使用哈希表了,但是如果我们想构建一个哈希表呢?本质上我们需要做的就是把一个字符串(比如 “狗”)映射到一个哈希代码(一个生成的数),即映射到一个数组的索引。你可能会问,为什么不直接使用索引呢?为什么要这么麻烦呢?因为通过这种方式我们可以直接查询 “狗” 并立即得到 “狗” 所在的位置,String name = Array["狗"] // 名字叫拉斯。而使用索引查询名称时,可能出现的情况是我们不知道名称所在的索引。比如,String name = Array[10] // 该名字现在叫鲍勃 - 那不是我的狗的名字。这就是把一个字符串映射到一个哈希代码的益处(对应于一个数组的索引而言)。我们可以通过使用模运算符和哈希表的大小来计算出数组的索引:index = hash_code % table_size

我们需要避免的另一种情况是两个关键字映射到同一个索引,这叫做哈希碰撞,如果哈希函数实现的不好,这很容易发生。实际上,每一个输入比输出多的哈希函数都有可能发生碰撞。通过下面的同一个函数的两个输出来展示一个简单的碰撞:

int cat_idx = hashCode("猫") % table_size; //cat_idx 现在等于 1
int dog_idx = hashCode("狗") % table_size; //dog_idx 也等于 1

我们可以看到,现在两个数组的索引均是 1 。这样将会出现两个值相互覆盖,因为它们被写到了相同的索引中。如果我们查找 “猫” 的值,将会返回 “拉斯” ,但是这并不是我们想要的。有许多可以解决哈希碰撞的方法,但是更受欢迎的一种方法叫做链接。链接的想法就是对于数组的每一个索引位置都有一个链表,如果碰撞发生,值就被存到链表中。因此,在前面的例子中,我们将会得到我们需要的值,但是我们需要搜索数组中索引为 1 的位置上的链表。伴有链接的哈希实现需要 O(1 + α) 时间,其中 α 是装载因子,它可以表示为 n/k,其中 n 是哈希表中的记录数目,k 是哈希表中可用位置的数目。但是请记住,只有当你给出的关键字非常随机时,这一结论才正确(依赖于 SUHA)。

这是做了一个很大的假设,因为总是有可能任何不相等的关键字都散列到同一点。这一问题的一个解决方法是去除哈希表中关键字对随机性的依赖,转而把随机性集中于关键字是如何被散列的,从而减少矛盾发生的可能性。这被称为……

通用散列

这个观念很简单,从 通用散列 universal hash 家族集合随机选择一个哈希函数 h 来计算哈希代码。换句话来说,就是选择任何一个随机的哈希函数来散列关键字。通过这种方法,两个不同的关键字的散列结果相同的可能性将非常低(LCTT 译注:原文是“not be the same”,应是笔误)。我只是简单的提一下,如果不相信我那么请相信数学。实现这一方法时需要注意的另一件事是如果选择了一个不好的通用散列家族,它会把时间和空间复杂度拖到 O(U),其中 U 是散列家族的大小。而其中的挑战就是找到一个不需要太多时间来计算,也不需要太多空间来存储的哈希家族。

上帝哈希函数

追求完美是人的天性。我们是否能够构建一个完美的哈希函数,从而能够把关键字映射到整数集中,并且几乎没有碰撞。好消息是我们能够在一定程度上做到,但是我们的数据必须是静态的(这意味着在一定时间内没有插入/删除/更新)。一个实现完美哈希函数的方法就是使用 2 级哈希 2-Level Hashing ,它基本上是我们前面讨论过的两种方法的组合。它使用通用散列来选择使用哪个哈希函数,然后通过链接组合起来,但是这次不是使用链表数据结构,而是使用另一个哈希表。让我们看一看下面它是怎么实现的:

 title=

但是这是如何工作的以及我们如何能够确保无需关心碰撞?

它的工作方式与生日悖论相反。它指出,在随机选择的一堆人中,会有一些人生日相同。但是如果一年中的天数远远大于人数(平方以上),那么有极大的可能性所有人的生日都不相同。所以这二者是如何相关的?对于每一个链接哈希表,其大小均为第一级哈希表大小的平方。那就是说,如果有两个元素被散列到同一个点,那么链接哈希表的大小将为 4 。大多数时候,链接哈希表将会非常稀疏/空。

重复下面两步来确保无需担心碰撞:

  • 从通用散列家族中选择一个哈希函数来计算
  • 如果发生碰撞,那么继续从通用散列家族中选择另一个哈希函数来计算

字面上看就是这样(这是一个 O(n^2) 空间的解)。如果需要考虑空间问题,那么显然需要另一个不同的方法。但是值得庆幸的是,该过程平均只需要进行两次

总结

只有具有一个好的哈希函数才能算得上是一个好的哈希表。在同时保证功能实现、时间和空间的提前下构建一个完美的哈希函数是一件很困难的事。我推荐你在解决问题的时候首先考虑哈希表,因为它能够为你提供巨大的性能优势,而且它能够对应用程序的可用性产生显著差异。哈希表和完美哈希函数常被用于实时编程应用中,并且在各种算法中都得到了广泛应用。你见或者不见,哈希表就在这儿。


via: http://www.zeroequalsfalse.press/2017/02/20/hashtables/

作者:Marty Jacobs 译者:ucasFL 校对:wxy

本文由 LCTT 原创编译,Linux中国 荣誉推出

不要让 git 命令中的错误抹去你数天的工作

 title=

今天我的同事几乎失去了他在四天工作中所做的一切。由于不正确的 git 命令,他把保存在 stash 中的更改删除了。在这悲伤的情节之后,我们试图寻找一种恢复他所做工作的方法,而且我们做到了!

首先警告一下:当你在实现一个大功能时,请将它分成小块并定期提交。长时间工作而不做提交并不是一个好主意。

现在我们已经搞定了那个错误,下面就演示一下怎样从 stash 中恢复误删的更改。

我用作示例的仓库中,只有一个源文件 “main.c”,如下所示:

 title=

它只有一次提交,即 “Initial commit”:

 title=

该文件的第一个版本是:

 title=

我将在文件中写一些代码。对于这个例子,我并不需要做什么大的改动,只需要有什么东西放进 stash 中即可,所以我们仅仅增加一行。“git diff” 的输出如下:

 title=

现在,假设我想从远程仓库中拉取一些新的更改,当时还不打算提交我自己的更改。于是,我决定先 stash 它,等拉取远程仓库中的更改后,再把我的更改恢复应用到主分支上。我执行下面的命令将我的更改移动到 stash 中:

git stash

使用命令 git stash list 查看 stash,在这里能看到我的更改:

 title=

我的代码已经在一个安全的地方,而且主分支目前是干净的(使用命令 git status 检查)。现在我只需要拉取远程仓库的更改,然后把我的更改恢复应用到主分支上,而且我也应该是这么做的。

但是我错误地执行了命令:

git stash drop

它删除了 stash,而不是执行了下面的命令:

git stash pop

这条命令会在从栈中删除 stash 之前应用它。如果我再次执行命令 git stash list,就能看到在没有从栈中将更改恢复到主分支的之前,我就删除了它。OMG!接下来怎么办?

好消息是:git 并没有删除包含了我的更改的对象,它只是移除了对它的引用。为了证明这一点,我使用命令 git fsck,它会验证数据库中对象的连接和有效性。这是我对该仓库执行了 git fsck 之后的输出:

 title=

由于使用了参数 --unreachable,我让 git-fsck 显示出所有不可访问的对象。正如你看到的,它显示并没有不可访问的对象。而当我从 stash 中删除了我的更改之后,再次执行相同的指令,得到了一个不一样的输出:

 title=

现在有三个不可访问对象。那么哪一个才是我的更改呢?实际上,我不知道。我需要通过执行命令 git show 来搜索每一个对象。

 title=

就是它!ID 号 95ccbd927ad4cd413ee2a28014c81454f4ede82c 对应了我的更改。现在我已经找到了丢失的更改,我可以恢复它。其中一种方法是将此 ID 取出来放进一个新的分支,或者直接提交它。如果你得到了你的更改对象的 ID 号,就可以决定以最好的方式,将更改再次恢复应用到主分支上。对于这个例子,我使用 git stash 将更改恢复到我的主分支上。

git stash apply 95ccbd927ad4cd413ee2a28014c81454f4ede82c

另外需要重点记住的是 git 会周期性地执行它的垃圾回收程序(gc),它执行之后,使用 git fsck 就不能再看到不可访问对象了。

本文最初发表于作者的博客,并得到了转载授权。

(题图:opensource.com,附图:José Guilherme Vanz, CC BY


via: https://opensource.com/article/17/8/recover-dropped-data-stash

作者:Jose Guilherme Vanz 译者:firmianay 校对:wxy

本文由 LCTT 原创编译,Linux中国 荣誉推出

在前几篇博文中我们学习了 DWARF 信息以及它如何使我们将机器码和上层源码联系起来。这一次我们通过为我们的调试器添加源码级逐步调试将该知识应用于实际。

系列文章索引

随着后面文章的发布,这些链接会逐渐生效。

  1. 准备环境
  2. 断点
  3. 寄存器和内存
  4. Elves 和 dwarves
  5. 源码和信号
  6. 源码级逐步执行
  7. 源码级断点
  8. 调用栈展开
  9. 读取变量
  10. 下一步

揭秘指令级逐步执行

我们正在超越了自我。首先让我们通过用户接口揭秘指令级单步执行。我决定将它切分为能被其它部分代码利用的 single_step_instruction 和确保是否启用了某个断点的 single_step_instruction_with_breakpoint_check 两个函数。

void debugger::single_step_instruction() {
    ptrace(PTRACE_SINGLESTEP, m_pid, nullptr, nullptr);
    wait_for_signal();
}

void debugger::single_step_instruction_with_breakpoint_check() {
    //首先,检查我们是否需要停用或者启用某个断点
    if (m_breakpoints.count(get_pc())) {
        step_over_breakpoint();
    }
    else {
        single_step_instruction();
    }
}

正如以往,另一个命令被集成到我们的 handle_command 函数:

else if(is_prefix(command, "stepi")) {
    single_step_instruction_with_breakpoint_check();
    auto line_entry = get_line_entry_from_pc(get_pc());
    print_source(line_entry->file->path, line_entry->line);
 }

利用新增的这些函数我们可以开始实现我们的源码级逐步执行函数。

实现逐步执行

我们打算编写这些函数非常简单的版本,但真正的调试器有 thread plan 的概念,它封装了所有的单步信息。例如,调试器可能有一些复杂的逻辑去决定断点的位置,然后有一些回调函数用于判断单步操作是否完成。这其中有非常多的基础设施,我们只采用一种朴素的方法。我们可能会意外地跳过断点,但如果你愿意的话,你可以花一些时间把所有的细节都处理好。

对于跳出 step_out,我们只是在函数的返回地址处设一个断点然后继续执行。我暂时还不想考虑调用栈展开的细节 - 这些都会在后面的部分介绍 - 但可以说返回地址就保存在栈帧开始的后 8 个字节中。因此我们会读取栈指针然后在内存相对应的地址读取值:

void debugger::step_out() {
    auto frame_pointer = get_register_value(m_pid, reg::rbp);
    auto return_address = read_memory(frame_pointer+8);

    bool should_remove_breakpoint = false;
    if (!m_breakpoints.count(return_address)) {
        set_breakpoint_at_address(return_address);
        should_remove_breakpoint = true;
    }

    continue_execution();

    if (should_remove_breakpoint) {
        remove_breakpoint(return_address);
    }
}

remove_breakpoint 是一个小的帮助函数:

void debugger::remove_breakpoint(std::intptr_t addr) {
    if (m_breakpoints.at(addr).is_enabled()) {
        m_breakpoints.at(addr).disable();
    }
    m_breakpoints.erase(addr);
}

接下来是跳入 step_in。一个简单的算法是继续逐步执行指令直到新的一行。

void debugger::step_in() {
   auto line = get_line_entry_from_pc(get_pc())->line;

    while (get_line_entry_from_pc(get_pc())->line == line) {
        single_step_instruction_with_breakpoint_check();
    }

    auto line_entry = get_line_entry_from_pc(get_pc());
    print_source(line_entry->file->path, line_entry->line);
}

跳过 step_over 对于我们来说是三个中最难的。理论上,解决方法就是在下一行源码中设置一个断点,但下一行源码是什么呢?它可能不是当前行后续的那一行,因为我们可能处于一个循环、或者某种条件结构之中。真正的调试器一般会检查当前正在执行什么指令然后计算出所有可能的分支目标,然后在所有分支目标中设置断点。对于一个小的项目,我不打算实现或者集成一个 x86 指令模拟器,因此我们要想一个更简单的解决办法。有几个可怕的选择,一个是一直逐步执行直到当前函数新的一行,或者在当前函数的每一行都设置一个断点。如果我们是要跳过一个函数调用,前者将会相当的低效,因为我们需要逐步执行那个调用图中的每个指令,因此我会采用第二种方法。

void debugger::step_over() {
    auto func = get_function_from_pc(get_pc());
    auto func_entry = at_low_pc(func);
    auto func_end = at_high_pc(func);

    auto line = get_line_entry_from_pc(func_entry);
    auto start_line = get_line_entry_from_pc(get_pc());

    std::vector<std::intptr_t> to_delete{};

    while (line->address < func_end) {
        if (line->address != start_line->address && !m_breakpoints.count(line->address)) {
            set_breakpoint_at_address(line->address);
            to_delete.push_back(line->address);
        }
        ++line;
    }

    auto frame_pointer = get_register_value(m_pid, reg::rbp);
    auto return_address = read_memory(frame_pointer+8);
    if (!m_breakpoints.count(return_address)) {
        set_breakpoint_at_address(return_address);
        to_delete.push_back(return_address);
    }

    continue_execution();

    for (auto addr : to_delete) {
        remove_breakpoint(addr);
    }
}

这个函数有一点复杂,我们将它拆开来看。

    auto func = get_function_from_pc(get_pc());
    auto func_entry = at_low_pc(func);
    auto func_end = at_high_pc(func);

at_low_pcat_high_pclibelfin 中的函数,它们能给我们指定函数 DWARF 信息条目的最小和最大程序计数器值。

    auto line = get_line_entry_from_pc(func_entry);
    auto start_line = get_line_entry_from_pc(get_pc());

    std::vector<std::intptr_t> breakpoints_to_remove{};

    while (line->address < func_end) {
        if (line->address != start_line->address && !m_breakpoints.count(line->address)) {
            set_breakpoint_at_address(line->address);
            breakpoints_to_remove.push_back(line->address);
        }
        ++line;
    }

我们需要移除我们设置的所有断点,以便不会泄露出我们的逐步执行函数,为此我们把它们保存到一个 std::vector 中。为了设置所有断点,我们循环遍历行表条目直到找到一个不在我们函数范围内的。对于每一个,我们都要确保它不是我们当前所在的行,而且在这个位置还没有设置任何断点。

    auto frame_pointer = get_register_value(m_pid, reg::rbp);
    auto return_address = read_memory(frame_pointer+8);
    if (!m_breakpoints.count(return_address)) {
        set_breakpoint_at_address(return_address);
        to_delete.push_back(return_address);
    }

这里我们在函数的返回地址处设置一个断点,正如跳出 step_out

    continue_execution();

    for (auto addr : to_delete) {
        remove_breakpoint(addr);
    }

最后,我们继续执行直到命中它们中的其中一个断点,然后移除所有我们设置的临时断点。

它并不美观,但暂时先这样吧。

当然,我们还需要将这个新功能添加到用户界面:

    else if(is_prefix(command, "step")) {
        step_in();
    }
    else if(is_prefix(command, "next")) {
        step_over();
    }
    else if(is_prefix(command, "finish")) {
        step_out();
    }

测试

我通过实现一个调用一系列不同函数的简单函数来进行测试:

void a() {
    int foo = 1;
}

void b() {
    int foo = 2;
    a();
}

void c() {
    int foo = 3;
    b();
}

void d() {
    int foo = 4;
    c();
}

void e() {
    int foo = 5;
    d();
}

void f() {
    int foo = 6;
    e();
}

int main() {
    f();
}

你应该可以在 main 地址处设置一个断点,然后在整个程序中跳入、跳过、跳出函数。如果你尝试跳出 main 函数或者跳入任何动态链接库,就会出现意料之外的事情。

你可以在这里找到这篇博文的相关代码。下次我们会利用我们新的 DWARF 技巧来实现源码级断点。


via: https://blog.tartanllama.xyz/c++/2017/05/06/writing-a-linux-debugger-dwarf-step/

作者:Simon Brand 译者:ictlyh 校对:wxy

本文由 LCTT 原创编译,Linux中国 荣誉推出

在上一部分我们学习了关于 DWARF 的信息,以及它如何被用于读取变量和将被执行的机器码与我们的高级语言的源码联系起来。在这一部分,我们将进入实践,实现一些我们调试器后面会使用的 DWARF 原语。我们也会利用这个机会,使我们的调试器可以在命中一个断点时打印出当前的源码上下文。

系列文章索引

随着后面文章的发布,这些链接会逐渐生效。

  1. 准备环境
  2. 断点
  3. 寄存器和内存
  4. Elves 和 dwarves
  5. 源码和信号
  6. 源码级逐步执行
  7. 源码级断点
  8. 调用栈展开
  9. 读取变量
  10. 下一步

设置我们的 DWARF 解析器

正如我在这系列文章开始时备注的,我们会使用 libelfin 来处理我们的 DWARF 信息。希望你已经在第一部分设置好了这些,如果没有的话,现在做吧,确保你使用我仓库的 fbreg 分支。

一旦你构建好了 libelfin,就可以把它添加到我们的调试器。第一步是解析我们的 ELF 可执行程序并从中提取 DWARF 信息。使用 libelfin 可以轻易实现,只需要对调试器作以下更改:

class debugger {
public:
    debugger (std::string prog_name, pid_t pid)
         : m_prog_name{std::move(prog_name)}, m_pid{pid} {
        auto fd = open(m_prog_name.c_str(), O_RDONLY);

        m_elf = elf::elf{elf::create_mmap_loader(fd)};
        m_dwarf = dwarf::dwarf{dwarf::elf::create_loader(m_elf)};
    }
    //...

private:
    //...
    dwarf::dwarf m_dwarf;
    elf::elf m_elf;
};

我们使用了 open 而不是 std::ifstream,因为 elf 加载器需要传递一个 UNIX 文件描述符给 mmap,从而可以将文件映射到内存而不是每次读取一部分。

调试信息原语

下一步我们可以实现从程序计数器的值中提取行条目(line entry)以及函数 DWARF 信息条目(function DIE)的函数。我们从 get_function_from_pc 开始:

dwarf::die debugger::get_function_from_pc(uint64_t pc) {
    for (auto &cu : m_dwarf.compilation_units()) {
        if (die_pc_range(cu.root()).contains(pc)) {
            for (const auto& die : cu.root()) {
                if (die.tag == dwarf::DW_TAG::subprogram) {
                    if (die_pc_range(die).contains(pc)) {
                        return die;
                    }
                }
            }
        }
    }

    throw std::out_of_range{"Cannot find function"};
}

这里我采用了朴素的方法,迭代遍历编译单元直到找到一个包含程序计数器的,然后迭代遍历它的子节点直到我们找到相关函数(DW_TAG_subprogram)。正如我在上一篇中提到的,如果你想要的话你可以处理类似的成员函数或者内联等情况。

接下来是 get_line_entry_from_pc

dwarf::line_table::iterator debugger::get_line_entry_from_pc(uint64_t pc) {
    for (auto &cu : m_dwarf.compilation_units()) {
        if (die_pc_range(cu.root()).contains(pc)) {
            auto &lt = cu.get_line_table();
            auto it = lt.find_address(pc);
            if (it == lt.end()) {
                throw std::out_of_range{"Cannot find line entry"};
            }
            else {
                return it;
            }
        }
    }

    throw std::out_of_range{"Cannot find line entry"};
}

同样,我们可以简单地找到正确的编译单元,然后查询行表获取相关的条目。

打印源码

当我们命中一个断点或者逐步执行我们的代码时,我们会想知道处于源码中的什么位置。

void debugger::print_source(const std::string& file_name, unsigned line, unsigned n_lines_context) {
    std::ifstream file {file_name};

    //获得一个所需行附近的窗口
    auto start_line = line <= n_lines_context ? 1 : line - n_lines_context;
    auto end_line = line + n_lines_context + (line < n_lines_context ? n_lines_context - line : 0) + 1;

    char c{};
    auto current_line = 1u;
    //跳过 start_line 之前的行
    while (current_line != start_line && file.get(c)) {
        if (c == '\n') {
            ++current_line;
        }
    }

    //如果我们在当前行则输出光标
    std::cout << (current_line==line ? "> " : "  ");

    //输出行直到 end_line
    while (current_line <= end_line && file.get(c)) {
        std::cout << c;
        if (c == '\n') {
            ++current_line;
            //如果我们在当前行则输出光标
            std::cout << (current_line==line ? "> " : "  ");
        }
    }

    //输出换行确保恰当地清空了流
    std::cout << std::endl;
}

现在我们可以打印出源码了,我们需要将这些通过钩子添加到我们的调试器。实现这个的一个好地方是当调试器从一个断点或者(最终)逐步执行得到一个信号时。到了这里,我们可能想要给我们的调试器添加一些更好的信号处理。

更好的信号处理

我们希望能够得知什么信号被发送给了进程,同样我们也想知道它是如何产生的。例如,我们希望能够得知是否由于命中了一个断点从而获得一个 SIGTRAP,还是由于逐步执行完成、或者是产生了一个新线程等等导致的。幸运的是,我们可以再一次使用 ptrace。可以给 ptrace 的一个命令是 PTRACE_GETSIGINFO,它会给你被发送给进程的最后一个信号的信息。我们类似这样使用它:

siginfo_t debugger::get_signal_info() {
    siginfo_t info;
    ptrace(PTRACE_GETSIGINFO, m_pid, nullptr, &info);
    return info;
}

这会给我们一个 siginfo_t 对象,它能提供以下信息:

siginfo_t {
    int      si_signo;     /* 信号编号 */
    int      si_errno;     /* errno 值 */
    int      si_code;      /* 信号代码 */
    int      si_trapno;    /* 导致生成硬件信号的陷阱编号
                              (大部分架构中都没有使用) */
    pid_t    si_pid;       /* 发送信号的进程 ID */
    uid_t    si_uid;       /* 发送信号进程的用户 ID */
    int      si_status;    /* 退出值或信号 */
    clock_t  si_utime;     /* 消耗的用户时间 */
    clock_t  si_stime;     /* 消耗的系统时间 */
    sigval_t si_value;     /* 信号值 */
    int      si_int;       /* POSIX.1b 信号 */
    void    *si_ptr;       /* POSIX.1b 信号 */
    int      si_overrun;   /* 计时器 overrun 计数;
                              POSIX.1b 计时器 */
    int      si_timerid;   /* 计时器 ID; POSIX.1b 计时器 */
    void    *si_addr;      /* 导致错误的内存地址 */
    long     si_band;      /* Band event (在 glibc 2.3.2 和之前版本中是 int 类型) */
    int      si_fd;        /* 文件描述符 */
    short    si_addr_lsb;  /* 地址的最不重要位
                              (自 Linux 2.6.32) */
    void    *si_lower;     /* 出现地址违规的下限 (自 Linux 3.19) */
    void    *si_upper;     /* 出现地址违规的上限 (自 Linux 3.19) */
    int      si_pkey;      /* PTE 上导致错误的保护键 (自 Linux 4.6) */
    void    *si_call_addr; /* 系统调用指令的地址
                              (自 Linux 3.5) */
    int      si_syscall;   /* 系统调用尝试次数
                              (自 Linux 3.5) */
    unsigned int si_arch;  /* 尝试系统调用的架构
                              (自 Linux 3.5) */
}

我只需要使用 si_signo 就可以找到被发送的信号,使用 si_code 来获取更多关于信号的信息。放置这些代码的最好位置是我们的 wait_for_signal 函数:

void debugger::wait_for_signal() {
    int wait_status;
    auto options = 0;
    waitpid(m_pid, &wait_status, options);

    auto siginfo = get_signal_info();

    switch (siginfo.si_signo) {
    case SIGTRAP:
        handle_sigtrap(siginfo);
        break;
    case SIGSEGV:
        std::cout << "Yay, segfault. Reason: " << siginfo.si_code << std::endl;
        break;
    default:
        std::cout << "Got signal " << strsignal(siginfo.si_signo) << std::endl;
    }
}

现在再来处理 SIGTRAP。知道当命中一个断点时会发送 SI_KERNELTRAP_BRKPT,而逐步执行结束时会发送 TRAP_TRACE 就足够了:

void debugger::handle_sigtrap(siginfo_t info) {
    switch (info.si_code) {
    //如果命中了一个断点其中的一个会被设置
    case SI_KERNEL:
    case TRAP_BRKPT:
    {
        set_pc(get_pc()-1); //将程序计数器的值设置为它应该指向的地方
        std::cout << "Hit breakpoint at address 0x" << std::hex << get_pc() << std::endl;
        auto line_entry = get_line_entry_from_pc(get_pc());
        print_source(line_entry->file->path, line_entry->line);
        return;
    }
    //如果信号是由逐步执行发送的,这会被设置
    case TRAP_TRACE:
        return;
    default:
        std::cout << "Unknown SIGTRAP code " << info.si_code << std::endl;
        return;
    }
}

这里有一大堆不同风格的信号你可以处理。查看 man sigaction 获取更多信息。

由于当我们收到 SIGTRAP 信号时我们已经修正了程序计数器的值,我们可以从 step_over_breakpoint 中移除这些代码,现在它看起来类似:

void debugger::step_over_breakpoint() {
    if (m_breakpoints.count(get_pc())) {
        auto& bp = m_breakpoints[get_pc()];
        if (bp.is_enabled()) {
            bp.disable();
            ptrace(PTRACE_SINGLESTEP, m_pid, nullptr, nullptr);
            wait_for_signal();
            bp.enable();
        }
    }
}

测试

现在你应该可以在某个地址设置断点,运行程序然后看到打印出了源码,而且正在被执行的行被光标标记了出来。

后面我们会添加设置源码级别断点的功能。同时,你可以从这里获取该博文的代码。


via: https://blog.tartanllama.xyz/c++/2017/04/24/writing-a-linux-debugger-source-signal/

作者:TartanLlama 译者:ictlyh 校对:wxy

本文由 LCTT 原创编译,Linux中国 荣誉推出