Exploring go pipelines and concurrency constructs

README.md

The serial version was my attempt for Stripe's CTF 3.

I then read an interesting post on go pipelines and tried to rewrite my version using those constructs. Obviously I don't understand it very well yet, since my rewrite is only twice as fast 😭. I was hoping for more on my quad-core machine.

Profiling might be hitting this issue.

benchmark.sh

 > time GOMAXPROCS=16 go run serial.go 000001 b27f65a2242a73fb2ca6496a1ee8ee9e7912fe9e 000000f0538d93e52853d901ec37bc177a6a5a4b 1391006506 
0000006b703772bda20992df5f6553ee2b2448ae
real	0m16.068s
user	0m18.646s
sys	0m5.387s


> time GOMAXPROCS=16 go run parallel.go 000001 b27f65a2242a73fb2ca6496a1ee8ee9e7912fe9e 000000f0538d93e52853d901ec37bc177a6a5a4b 1391006506 
0000006b703772bda20992df5f6553ee2b2448ae
real	0m7.432s
user	0m40.740s
sys	0m5.860s

parallel.go

package main

import (
	"crypto/sha1"
	"encoding/hex"
	"fmt"
	"io"
	"io/ioutil"
	"log"
	"os"
	"os/exec"
	"strconv"
)

func main() {
	difficulty, tree, parent, timestamp := os.Args[1], os.Args[2], os.Args[3], os.Args[4]
	body := fmt.Sprintf(`tree %s
parent %s
author CTF user <[email protected]> %s +0000
committer CTF user <[email protected]> %s +0000

Mined a Gitcoin! `, tree, parent, timestamp, timestamp)

	result := findSha1(body, difficulty)
	if result.err != nil {
		fmt.Println(result.err)
		return
	}
	writeGitObject(result.msg)
	fmt.Printf(result.sha1)
}

type result struct {
	sha1 string
	msg  string
	err  error
}

func findSha1(body string, difficulty string) result {
	// fmt.Println(difficulty)

	messages := produce(body)
	outcome := make(chan result)

	const numWorkers = 10
	for i := 0; i < numWorkers; i++ {
		go consume(messages, difficulty, outcome)
	}

	return <-outcome
}

func consume(messages <-chan string, difficulty string, c chan<- result) {
	for msg := range messages {
		header := fmt.Sprintf("commit %d\000", len(msg))
		content := header + msg

		hasher := sha1.New()
		io.WriteString(hasher, content)
		sha1 := hex.EncodeToString(hasher.Sum(nil))

		if sha1 < difficulty {
			c <- result{sha1, msg, nil}
		}
	}
}

func writeGitObject(msg string) {
	os.Chdir("level1")
	cmd := exec.Command("git", "hash-object", "-t", "commit", "-w", "--stdin")
	stdin, err := cmd.StdinPipe()
	if err != nil {
		log.Fatalf("Problem getting stdin: %s", err)
	}
	stderr, err := cmd.StderrPipe()
	if err != nil {
		log.Fatalf("Problem getting stderr: %s", err)
	}
	stderrC := make(chan string)
	go func() {
		out, err := ioutil.ReadAll(stderr)
		if err == nil {
			stderrC <- string(out)
		} else {
			stderrC <- err.Error()
		}
	}()
	err = cmd.Start()
	if err != nil {
		log.Fatalf("Problem starting the command: %s", err)
	}
	n, err := io.WriteString(stdin, msg)
	if n != len(msg) {
		log.Fatalf("expected to write %d but wrote %d", len(msg), n)
	}
	if err != nil {
		log.Fatal(err)
	}
	if err = stdin.Close(); err != nil {
		log.Fatal(err)
	}
	err = cmd.Wait()
	if err != nil {
		log.Fatalf("%s\n\n%s\n", err, <-stderrC)
	}
}

func produce(body string) chan string {
	yield := make(chan string)
	count := 0
	go func() {
		for {
			yield <- body + strconv.Itoa(count)
			count++
		}
	}()
	return yield
}

Profiling.sh

master %  scala ~/Projects/stripe-ctf-3/level1 > go tool pprof solve parallel.prof
Welcome to pprof!  For help, type 'help'.
(pprof) topN
Total: 3501 samples
    2696  77.0%  77.0%     2696  77.0% runtime.mach_semaphore_wait
     227   6.5%  83.5%      227   6.5% runtime.usleep
      95   2.7%  86.2%       95   2.7% crypto/sha1.block
      50   1.4%  87.6%       50   1.4% runtime.mach_semaphore_timedwait
      39   1.1%  88.7%       39   1.1% runtime.casp
      26   0.7%  89.5%      136   3.9% runtime.mallocgc
      24   0.7%  90.2%       24   0.7% runtime.memmove
      23   0.7%  90.8%       23   0.7% runtime.mach_semaphore_signal
      20   0.6%  91.4%       38   1.1% fmt.(*pp).doPrintf
      20   0.6%  92.0%       20   0.6% sweepspan

serial.go

package main

import (
  "crypto/sha1"
  "encoding/hex"
  "fmt"
  "io"
  "io/ioutil"
  "log"
  "os"
  "os/exec"
  "strconv"
)

func main() {
  difficulty, tree, parent, timestamp := os.Args[1], os.Args[2], os.Args[3], os.Args[4]
  body := fmt.Sprintf(`tree %s
parent %s
author CTF user <[email protected]> %s +0000
committer CTF user <[email protected]> %s +0000

Mined a Gitcoin! `, tree, parent, timestamp, timestamp)

  // fmt.Println(difficulty)

  for counter := 0; ;counter++ {
    msg := body + strconv.Itoa(counter)
    // fmt.Println([]byte(msg))

    header := fmt.Sprintf("commit %d\000", len(msg))
    // fmt.Println([]byte(header))

    content := header + msg
    // fmt.Println([]byte(content))
    // fmt.Println(content)

    hasher := sha1.New()
    io.WriteString(hasher, content)
    sha1 := hex.EncodeToString(hasher.Sum(nil))

    // fmt.Println(sha1)
    // break

    if sha1 < difficulty {
      // fmt.Printf("%d,%s\n", counter, sha1)
      // fmt.Printf("%s", content)
      os.Chdir("level1")
      cmd := exec.Command("git", "hash-object", "-t", "commit", "-w", "--stdin")
      stdin, err := cmd.StdinPipe()
      if err != nil {
        log.Fatalf("Problem getting stdin: %s", err)
      }
      stderr, err := cmd.StderrPipe()
      if err != nil {
        log.Fatalf("Problem getting stderr: %s", err)
      }
      stderrC := make(chan string)
      go func() {
        out, err := ioutil.ReadAll(stderr)
        if err == nil {
          stderrC <- string(out)
        } else {
          stderrC <- err.Error()
        }
      }()
      err = cmd.Start()
      if err != nil {
        log.Fatalf("Problem starting the command: %s", err)
      }
      n, err := io.WriteString(stdin, msg)
      if n != len(msg) {
        log.Fatalf("expected to write %d but wrote %d", len(msg), n)
      }
      if err != nil {
        log.Fatal(err)
      }
      if err = stdin.Close(); err != nil {
        log.Fatal(err)
      }
      err = cmd.Wait()
      if err != nil {
        log.Fatalf("%s\n\n%s\n", err, <- stderrC)
      }
      fmt.Printf(sha1)
      break
    // } else if (counter % 10000 == 0) {
    //   fmt.Print(".")
    }
  }

}