From owner-freebsd-smp@FreeBSD.ORG Mon Jun 2 13:37:31 2008 Return-Path: Delivered-To: freebsd-smp@freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:4f8:fff6::34]) by hub.freebsd.org (Postfix) with ESMTP id 1570E1065671 for ; Mon, 2 Jun 2008 13:37:31 +0000 (UTC) (envelope-from asmrookie@gmail.com) Received: from fg-out-1718.google.com (fg-out-1718.google.com [72.14.220.156]) by mx1.freebsd.org (Postfix) with ESMTP id 72F838FC15 for ; Mon, 2 Jun 2008 13:37:30 +0000 (UTC) (envelope-from asmrookie@gmail.com) Received: by fg-out-1718.google.com with SMTP id l26so891474fgb.35 for ; Mon, 02 Jun 2008 06:37:29 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:received:received:message-id:date:from:sender:to:subject:mime-version:content-type:x-google-sender-auth; bh=c5o5DUZoW3AVH2+aHceo7YmH7BTQ+G1m5X2bIV8UT/g=; b=tUJTiR/BjUK9/CQID0vGRW0vr2RfKEuvEcMsb5CPtDDoWNQxEITubPRSMVNZ7yOZp7hSjTOCk8oW+3mcditUirSeTAlvIbALYi1rcbeT5agswo03094Va3waIEhzD8ZFd7n4qsGAtwEQ6mUa48Uoag0y5fYD3Dy4Fgd7ducvZiM= DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=message-id:date:from:sender:to:subject:mime-version:content-type:x-google-sender-auth; b=YYeLBBmcFBgtGY5s5ZmA1c8H1nahVsOuHGx+uA32UQVPUXAv7Tew+4J2ewYcqi7GILNbUV7IpVMzAslD2jbe0OnbpaMeKt3z7elh/Db7hMzq0Vr9TK7pnPhjtRiedKgMRN3gf7F0RrHRwZvv+xCsW4c7BkbPxGpWxFziihasPAU= Received: by 10.86.60.15 with SMTP id i15mr1907687fga.53.1212412338908; Mon, 02 Jun 2008 06:12:18 -0700 (PDT) Received: by 10.86.2.18 with HTTP; Mon, 2 Jun 2008 06:12:18 -0700 (PDT) Message-ID: <3bbf2fe10806020612y68883b00n967f5ee88c15771f@mail.gmail.com> Date: Mon, 2 Jun 2008 15:12:18 +0200 From: "Attilio Rao" Sender: asmrookie@gmail.com To: freebsd-smp@freebsd.org, "John Baldwin" , "Jeff Roberson" , "Kris Kennaway" MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="----=_Part_12684_3799776.1212412338895" X-Google-Sender-Auth: fe2fe67dcbf1d22c Cc: Subject: [PATCH] back-off algorithm for spinning X-BeenThere: freebsd-smp@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: FreeBSD SMP implementation group List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Mon, 02 Jun 2008 13:37:31 -0000 ------=_Part_12684_3799776.1212412338895 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 7bit Content-Disposition: inline The attached patch implements a back-off algorithm for adaptive spinning in order to reduce cache traffics in big SMP environments. I really need to tune values (CAP and SHIFT) on a big SMP machine (16/32 ways possibily) and currently I have no-one available. Some tips: - uint32_t has been choosen for the back-off counters as we want a fixed size because we want to have a deterministic size for words - Possibily, in the spinlock case, the loop for the first number of loop counting can be reduced now, but we still need to maintain the same difference between this and the later value for determining "spinlock held too long". Revisions are appreciated. Thanks, Attilio -- Peace can only be achieved by understanding - A. Einstein ------=_Part_12684_3799776.1212412338895 Content-Type: application/octet-stream; name=lock_backoff.diff Content-Transfer-Encoding: base64 X-Attachment-Id: f_fgz2z066 Content-Disposition: attachment; filename=lock_backoff.diff LS0tIC91c3Ivc3JjL3N5cy9rZXJuL2tlcm5fbXV0ZXguYwkyMDA4LTA1LTMxIDIzOjQyOjE0LjAw MDAwMDAwMCArMDIwMAorKysgc3lzL2tlcm4va2Vybl9tdXRleC5jCTIwMDgtMDYtMDIgMDA6MTI6 MjYuMDAwMDAwMDAwICswMjAwCkBAIC0xMjMsNiArMTIzLDI2IEBACiBzdHJ1Y3QgbXR4IGJsb2Nr ZWRfbG9jazsKIHN0cnVjdCBtdHggR2lhbnQ7CiAKKyNpZmRlZiBBREFQVElWRV9NVVRFWEVTCitz dGF0aWMgX19pbmxpbmUgdm9pZAorbXR4X2FkYXB0X3NwaW4oc3RydWN0IG10eCAqbSwgdm9sYXRp bGUgc3RydWN0IHRocmVhZCAqb3duZXIpCit7CisJdWludDMyX3QgYmFja29mZiwgdGJhY2s7CisK KwkvKgorCSAqIFVzZSBhIGJhY2stb2ZmIGNvdW50ZXIgaW4gb3JkZXIgdG8gcmVkdWNlIGNhY2hl cyB0cmFmZmljIHdoZW4KKwkgKiByZWFkaW5nIHRoZSBsb2NrIHN0YXRlLgorCSAqLworCWZvciAo YmFja29mZiA9IExPQ0tfQkFDS09GRl9JTklUOyBtdHhfb3duZXIobSkgPT0gb3duZXIgJiYKKwkg ICAgVERfSVNfUlVOTklORyhvd25lcik7IGJhY2tvZmYgPDw9IExPQ0tfQkFDS09GRl9TSElGVCkg eworCQlpZiAoYmFja29mZiA+IExPQ0tfQkFDS09GRl9DQVApCisJCQliYWNrb2ZmID0gTE9DS19C QUNLT0ZGX0NBUDsKKwkJZm9yICh0YmFjayA9IDA7IHRiYWNrICE9IGJhY2tvZmY7IHRiYWNrKysp CisJCQljcHVfc3BpbndhaXQoKTsKKwl9Cit9CisjZW5kaWYKKwogdm9pZAogYXNzZXJ0X210eChz dHJ1Y3QgbG9ja19vYmplY3QgKmxvY2ssIGludCB3aGF0KQogewpAQCAtMzM4LDkgKzM1OCw3IEBA CiAJCQkJCUNUUjMoS1RSX0xPQ0ssCiAJCQkJCSAgICAiJXM6IHNwaW5uaW5nIG9uICVwIGhlbGQg YnkgJXAiLAogCQkJCQkgICAgX19mdW5jX18sIG0sIG93bmVyKTsKLQkJCQl3aGlsZSAobXR4X293 bmVyKG0pID09IG93bmVyICYmCi0JCQkJICAgIFREX0lTX1JVTk5JTkcob3duZXIpKQotCQkJCQlj cHVfc3BpbndhaXQoKTsKKwkJCQltdHhfYWRhcHRfc3BpbihtLCBvd25lcik7CiAJCQkJY29udGlu dWU7CiAJCQl9CiAJCX0KQEAgLTQ0OCw2ICs0NjYsNyBAQAogX210eF9sb2NrX3NwaW4oc3RydWN0 IG10eCAqbSwgdWludHB0cl90IHRpZCwgaW50IG9wdHMsIGNvbnN0IGNoYXIgKmZpbGUsCiAgICAg aW50IGxpbmUpCiB7CisJdWludDMyX3QgYmFja29mZiwgdGJhY2s7CiAJaW50IGkgPSAwLCBjb250 ZXN0ZWQgPSAwOwogCXVpbnQ2NF90IHdhaXR0aW1lID0gMDsKIAkKQEAgLTQ1OSw5ICs0NzgsMTQg QEAKIAogCQkvKiBHaXZlIGludGVycnVwdHMgYSBjaGFuY2Ugd2hpbGUgd2Ugc3Bpbi4gKi8KIAkJ c3BpbmxvY2tfZXhpdCgpOworCQliYWNrb2ZmID0gTE9DS19CQUNLT0ZGX0lOSVQ7CiAJCXdoaWxl IChtLT5tdHhfbG9jayAhPSBNVFhfVU5PV05FRCkgewogCQkJaWYgKGkrKyA8IDEwMDAwMDAwKSB7 Ci0JCQkJY3B1X3NwaW53YWl0KCk7CisJCQkJaWYgKGJhY2tvZmYgPiBMT0NLX0JBQ0tPRkZfQ0FQ KQorCQkJCQliYWNrb2ZmID0gTE9DS19CQUNLT0ZGX0NBUDsKKwkJCQlmb3IgKHRiYWNrID0gMDsg dGJhY2sgIT0gYmFja29mZjsgdGJhY2srKykKKwkJCQkJY3B1X3NwaW53YWl0KCk7CisJCQkJYmFj a29mZiA8PD0gTE9DS19CQUNLT0ZGX1NISUZUOwogCQkJCWNvbnRpbnVlOwogCQkJfQogCQkJaWYg KGkgPCA2MDAwMDAwMCB8fCBrZGJfYWN0aXZlIHx8IHBhbmljc3RyICE9IE5VTEwpCkBAIC00ODgs NiArNTEyLDcgQEAKIAl1aW50cHRyX3QgdGlkOwogCWludCBpLCBjb250ZXN0ZWQ7CiAJdWludDY0 X3Qgd2FpdHRpbWU7CisJdWludDMyX3QgYmFja29mZiwgdGJhY2s7CiAKIAljb250ZXN0ZWQgPSBp ID0gMDsKIAl3YWl0dGltZSA9IDA7CkBAIC01MTYsMTAgKzU0MSwxNiBAQAogCQkJICAgICZjb250 ZXN0ZWQsICZ3YWl0dGltZSk7CiAJCQkvKiBHaXZlIGludGVycnVwdHMgYSBjaGFuY2Ugd2hpbGUg d2Ugc3Bpbi4gKi8KIAkJCXNwaW5sb2NrX2V4aXQoKTsKKwkJCWJhY2tvZmYgPSBMT0NLX0JBQ0tP RkZfSU5JVDsKIAkJCXdoaWxlIChtLT5tdHhfbG9jayAhPSBNVFhfVU5PV05FRCkgewotCQkJCWlm IChpKysgPCAxMDAwMDAwMCkKLQkJCQkJY3B1X3NwaW53YWl0KCk7Ci0JCQkJZWxzZSBpZiAoaSA8 IDYwMDAwMDAwIHx8CisJCQkJaWYgKGkrKyA8IDEwMDAwMDAwKSB7CisJCQkJCWlmIChiYWNrb2Zm ID4gTE9DS19CQUNLT0ZGX0NBUCkKKwkJCQkJCWJhY2tvZmYgPSBMT0NLX0JBQ0tPRkZfQ0FQOwor CQkJCQlmb3IgKHRiYWNrID0gMDsgdGJhY2sgIT0gYmFja29mZjsKKwkJCQkJICAgIHRiYWNrKysp CisJCQkJCQljcHVfc3BpbndhaXQoKTsKKwkJCQkJYmFja29mZiA8PD0gTE9DS19CQUNLT0ZGX1NI SUZUOworCQkJCX0gZWxzZSBpZiAoaSA8IDYwMDAwMDAwIHx8CiAJCQkJICAgIGtkYl9hY3RpdmUg fHwgcGFuaWNzdHIgIT0gTlVMTCkKIAkJCQkJREVMQVkoMSk7CiAJCQkJZWxzZQotLS0gL3Vzci9z cmMvc3lzL2tlcm4va2Vybl9yd2xvY2suYwkyMDA4LTA1LTMxIDIzOjQyOjE1LjAwMDAwMDAwMCAr MDIwMAorKysgc3lzL2tlcm4va2Vybl9yd2xvY2suYwkyMDA4LTA2LTAxIDIzOjMyOjI0LjAwMDAw MDAwMCArMDIwMApAQCAtMTE0LDYgKzExNCwyNyBAQAogI2RlZmluZQlfcndfYXNzZXJ0KHJ3LCB3 aGF0LCBmaWxlLCBsaW5lKQogI2VuZGlmCiAKKyNpZmRlZiBBREFQVElWRV9SV0xPQ0tTCitzdGF0 aWMgX19pbmxpbmUgdm9pZAorcndfYWRhcHRfc3BpbihzdHJ1Y3Qgcndsb2NrICpydywgdm9sYXRp bGUgc3RydWN0IHRocmVhZCAqb3duZXIpCit7CisJdWludDMyX3QgYmFja29mZiwgdGJhY2s7CisK KwkvKgorCSAqIFVzZSBhIGJhY2stb2ZmIGNvdW50ZXIgaW4gb3JkZXIgdG8gcmVkdWNlIGNhY2hl cyB0cmFmZmljIHdoZW4KKwkgKiByZWFkaW5nIHRoZSBsb2NrIHN0YXRlLgorCSAqLworCWZvciAo YmFja29mZiA9IExPQ0tfQkFDS09GRl9JTklUOyBvd25lciA9PQorCSAgICAoc3RydWN0IHRocmVh ZCopUldfT1dORVIocnctPnJ3X2xvY2spICYmIFREX0lTX1JVTk5JTkcob3duZXIpOworCSAgICBi YWNrb2ZmIDw8PSBMT0NLX0JBQ0tPRkZfU0hJRlQpIHsKKwkJaWYgKGJhY2tvZmYgPiBMT0NLX0JB Q0tPRkZfQ0FQKQorCQkJYmFja29mZiA9IExPQ0tfQkFDS09GRl9DQVA7CisJCWZvciAodGJhY2sg PSAwOyB0YmFjayAhPSBiYWNrb2ZmOyB0YmFjaysrKQorCQkJY3B1X3NwaW53YWl0KCk7CisJfQor fQorI2VuZGlmCisKIHZvaWQKIGFzc2VydF9ydyhzdHJ1Y3QgbG9ja19vYmplY3QgKmxvY2ssIGlu dCB3aGF0KQogewpAQCAtMjcxLDggKzI5Miw3IEBACiAJc3RydWN0IHR1cm5zdGlsZSAqdHM7CiAj aWZkZWYgQURBUFRJVkVfUldMT0NLUwogCXZvbGF0aWxlIHN0cnVjdCB0aHJlYWQgKm93bmVyOwot CWludCBzcGludHJpZXMgPSAwOwotCWludCBpOworCWludCBpLCBzcGludHJpZXMgPSAwOwogI2Vu ZGlmCiAJdWludDY0X3Qgd2FpdHRpbWUgPSAwOwogCWludCBjb250ZXN0ZWQgPSAwOwpAQCAtMzMx LDkgKzM1MSw3IEBACiAJCQkJCUNUUjMoS1RSX0xPQ0ssCiAJCQkJCSAgICAiJXM6IHNwaW5uaW5n IG9uICVwIGhlbGQgYnkgJXAiLAogCQkJCQkgICAgX19mdW5jX18sIHJ3LCBvd25lcik7Ci0JCQkJ d2hpbGUgKChzdHJ1Y3QgdGhyZWFkKilSV19PV05FUihydy0+cndfbG9jaykgPT0KLQkJCQkgICAg b3duZXIgJiYgVERfSVNfUlVOTklORyhvd25lcikpCi0JCQkJCWNwdV9zcGlud2FpdCgpOworCQkJ CXJ3X2FkYXB0X3NwaW4ocncsIG93bmVyKTsKIAkJCQljb250aW51ZTsKIAkJCX0KIAkJfSBlbHNl IGlmIChzcGludHJpZXMgPCByb3duZXJfcmV0cmllcykgewpAQCAtNTczLDggKzU5MSw3IEBACiAJ c3RydWN0IHR1cm5zdGlsZSAqdHM7CiAjaWZkZWYgQURBUFRJVkVfUldMT0NLUwogCXZvbGF0aWxl IHN0cnVjdCB0aHJlYWQgKm93bmVyOwotCWludCBzcGludHJpZXMgPSAwOwotCWludCBpOworCWlu dCBpLCBzcGludHJpZXMgPSAwOwogI2VuZGlmCiAJdWludDY0X3Qgd2FpdHRpbWUgPSAwOwogCXVp bnRwdHJfdCB2LCB4OwpAQCAtNjA5LDkgKzYyNiw3IEBACiAJCQlpZiAoTE9DS19MT0dfVEVTVCgm cnctPmxvY2tfb2JqZWN0LCAwKSkKIAkJCQlDVFIzKEtUUl9MT0NLLCAiJXM6IHNwaW5uaW5nIG9u ICVwIGhlbGQgYnkgJXAiLAogCQkJCSAgICBfX2Z1bmNfXywgcncsIG93bmVyKTsKLQkJCXdoaWxl ICgoc3RydWN0IHRocmVhZCopUldfT1dORVIocnctPnJ3X2xvY2spID09IG93bmVyICYmCi0JCQkg ICAgVERfSVNfUlVOTklORyhvd25lcikpCi0JCQkJY3B1X3NwaW53YWl0KCk7CisJCQlyd19hZGFw dF9zcGluKHJ3LCBvd25lcik7CiAJCQljb250aW51ZTsKIAkJfQogCQlpZiAoKHYgJiBSV19MT0NL X1JFQUQpICYmIFJXX1JFQURFUlModikgJiYKLS0tIC91c3Ivc3JjL3N5cy9rZXJuL2tlcm5fc3gu YwkyMDA4LTA1LTMxIDIzOjQyOjE1LjAwMDAwMDAwMCArMDIwMAorKysgc3lzL2tlcm4va2Vybl9z eC5jCTIwMDgtMDYtMDEgMjM6NDA6MjIuMDAwMDAwMDAwICswMjAwCkBAIC0xMjYsNiArMTI2LDI3 IEBACiAjZGVmaW5lCV9zeF9hc3NlcnQoc3gsIHdoYXQsIGZpbGUsIGxpbmUpCiAjZW5kaWYKIAor I2lmZGVmIEFEQVBUSVZFX1NYCitzdGF0aWMgX19pbmxpbmUgdm9pZAorc3hfYWRhcHRfc3Bpbihz dHJ1Y3Qgc3ggKnN4LCB2b2xhdGlsZSBzdHJ1Y3QgdGhyZWFkICpvd25lcikKK3sKKwl1aW50MzJf dCBiYWNrb2ZmLCB0YmFjazsKKworCS8qCisJICogVXNlIGEgYmFjay1vZmYgY291bnRlciBpbiBv cmRlciB0byByZWR1Y2UgY2FjaGVzIHRyYWZmaWMgd2hlbgorCSAqIHJlYWRpbmcgdGhlIGxvY2sg c3RhdGUuCisJICovCisJZm9yIChiYWNrb2ZmID0gTE9DS19CQUNLT0ZGX0lOSVQ7IG93bmVyID09 CisJICAgIChzdHJ1Y3QgdGhyZWFkICopU1hfT1dORVIoc3gtPnN4X2xvY2spICYmIFREX0lTX1JV Tk5JTkcob3duZXIpOworCSAgICBiYWNrb2ZmIDw8PSBMT0NLX0JBQ0tPRkZfU0hJRlQpIHsKKwkJ aWYgKGJhY2tvZmYgPiBMT0NLX0JBQ0tPRkZfQ0FQKQorCQkJYmFja29mZiA9IExPQ0tfQkFDS09G Rl9DQVA7CisJCWZvciAodGJhY2sgPSAwOyB0YmFjayAhPSBiYWNrb2ZmOyB0YmFjaysrKQorCQkJ Y3B1X3NwaW53YWl0KCk7CisJfQorfQorI2VuZGlmCisKIHZvaWQKIGFzc2VydF9zeChzdHJ1Y3Qg bG9ja19vYmplY3QgKmxvY2ssIGludCB3aGF0KQogewpAQCAtNDY2LDkgKzQ4Nyw3IEBACiAJCQkJ CSAgICAiJXM6IHNwaW5uaW5nIG9uICVwIGhlbGQgYnkgJXAiLAogCQkJCQkgICAgX19mdW5jX18s IHN4LCBvd25lcik7CiAJCQkJR0lBTlRfU0FWRSgpOwotCQkJCXdoaWxlIChTWF9PV05FUihzeC0+ c3hfbG9jaykgPT0geCAmJgotCQkJCSAgICBURF9JU19SVU5OSU5HKG93bmVyKSkKLQkJCQkJY3B1 X3NwaW53YWl0KCk7CisJCQkJc3hfYWRhcHRfc3BpbihzeCwgb3duZXIpOwogCQkJCWNvbnRpbnVl OwogCQkJfQogCQl9CkBAIC02OTMsOSArNzEyLDcgQEAKIAkJCQkJICAgICIlczogc3Bpbm5pbmcg b24gJXAgaGVsZCBieSAlcCIsCiAJCQkJCSAgICBfX2Z1bmNfXywgc3gsIG93bmVyKTsKIAkJCQlH SUFOVF9TQVZFKCk7Ci0JCQkJd2hpbGUgKFNYX09XTkVSKHN4LT5zeF9sb2NrKSA9PSB4ICYmCi0J CQkJICAgIFREX0lTX1JVTk5JTkcob3duZXIpKQotCQkJCQljcHVfc3BpbndhaXQoKTsKKwkJCQlz eF9hZGFwdF9zcGluKHN4LCBvd25lcik7CiAJCQkJY29udGludWU7CiAJCQl9CiAJCX0KLS0tIC91 c3Ivc3JjL3N5cy9zeXMvbG9jay5oCTIwMDgtMDUtMzEgMjM6NDU6MTMuMDAwMDAwMDAwICswMjAw CisrKyBzeXMvc3lzL2xvY2suaAkyMDA4LTA2LTAyIDEyOjQ1OjM1LjAwMDAwMDAwMCArMDIwMApA QCAtMTg2LDYgKzE4NiwxMyBAQAogI2RlZmluZSBNUEFTUzQoZXgsIHdoYXQsIGZpbGUsIGxpbmUp CQkJCQlcCiAJS0FTU0VSVCgoZXgpLCAoIkFzc2VydGlvbiAlcyBmYWlsZWQgYXQgJXM6JWQiLCB3 aGF0LCBmaWxlLCBsaW5lKSkKIAorLyoKKyAqIEJhY2stb2ZmIGNvdW50ZXJzIGhhbmRsaW5nIG1h Y3Jvcy4KKyAqLworI2RlZmluZQlMT0NLX0JBQ0tPRkZfQ0FQCTB4NDAwMDAKKyNkZWZpbmUJTE9D S19CQUNLT0ZGX0lOSVQJMHgwMQorI2RlZmluZQlMT0NLX0JBQ0tPRkZfU0hJRlQJMHgwMQorCiBl eHRlcm4gc3RydWN0IGxvY2tfY2xhc3MgbG9ja19jbGFzc19tdHhfc2xlZXA7CiBleHRlcm4gc3Ry dWN0IGxvY2tfY2xhc3MgbG9ja19jbGFzc19tdHhfc3BpbjsKIGV4dGVybiBzdHJ1Y3QgbG9ja19j bGFzcyBsb2NrX2NsYXNzX3N4Owo= ------=_Part_12684_3799776.1212412338895--